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

248 - Strobogrammatic Number III

Question

Algorithm

Code

All Problems

All Solutions