Question
Formatted question description: https://leetcode.ca/all/248.html
248 Strobogrammatic Number III
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.
Example:
Input: low = "50", high = "100"
Output: 3
Explanation: 69, 88, and 96 are three strobogrammatic numbers.
Note:
Because the range might be a large number, the lowand high numbers are represented as string.
Algorithm
Goal is to get the number of symmetry
numbers in a given range.
Initialize the cases of n=0
and n=1
, and then recurse based on them.
The recursion length len is traversed from low to high, and then see if the current word length reaches len,
- If it is reached, first remove the multiple digits that start with 0,
- Then remove the numbers with the same length as low but less than low, and numbers with the same length as high but greater than high,
- Then the result is incremented by 1,
- Then add the five pairs of symmetric numbers to the left and right of the current word, and continue to call recursively
Code
Java
-
public class Strobogrammatic_Number_III { public static void main(String[] args) { Strobogrammatic_Number_III out = new Strobogrammatic_Number_III(); Solution s = out.new Solution(); System.out.println(s.strobogrammaticInRange("50", "100")); } public class Solution { int res = 0; public int strobogrammaticInRange(String low, String high) { if (low == null || high == null) { return res; } for (int i = low.length(); i <= high.length(); ++i) { dfs(low, high, "", i); dfs(low, high, "0", i); dfs(low, high, "1", i); dfs(low, high, "8", i); } return res; } void dfs(String low, String high, String path, int len) { if (path.length() >= len) { if (path.length() != len || (len != 1 && path.charAt(0) == '0')) { return; } if ((len == low.length() && path.compareTo(low) < 0) || (len == high.length() && path.compareTo(high) > 0)) { return; } ++res; } dfs(low, high, "0" + path + "0", len); dfs(low, high, "1" + path + "1", len); dfs(low, high, "6" + path + "9", len); dfs(low, high, "8" + path + "8", len); dfs(low, high, "9" + path + "6", len); } } }
-
Todo
-
class Solution(object): def findStrobogrammatic(self, n): """ :type n: int :rtype: List[str] """ self.d = {"0": "0", "1": "1", "6": "9", "8": "8", "9": "6"} def dfs(half, path, n): if len(path) == half: pathStr = "".join(path) if half * 2 == n: toAppend = pathStr + "".join([self.d[x] for x in pathStr[::-1]]) toAppendInt = int(toAppend) if self.low <= toAppendInt <= self.high: self.count += 1 else: for c in "018": toAppend = pathStr + c + "".join([self.d[x] for x in pathStr[::-1]]) toAppendInt = int(toAppend) if self.low <= toAppendInt <= self.high: self.count += 1 return for c in "01689": if c == "0" and len(path) == 0: continue path.append(c) dfs(half, path, n) path.pop() res = [] dfs(n / 2, [], n) return res def strobogrammaticInRange(self, low, high): """ :type low: str :type high: str :rtype: int """ if int(low) > int(high): return 0 self.count = 0 self.low = int(low) self.high = int(high) for length in range(len(low), len(high) + 1): self.findStrobogrammatic(length) return self.count