A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.
For example,
Given low = "50", high = "100", return 3. Because 69, 88, and 96 are three strobogrammatic numbers.
Given low = "50", high = "100", return 3. Because 69, 88, and 96 are three strobogrammatic numbers.
Note:
Because the range might be a large number, the low and high numbers are represented as string.
Because the range might be a large number, the low and high numbers are represented as string.
Solution:
Starting from arbitrary string with length from len(low to len(high), constructing strobogrammatic while doing DFS. From outside to inside, in each iteration, wrap up current string using a pair of strobogrammatic number. Check whether the string is within the range in between low and high when wrapping is over.
No comments:
Post a Comment