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
    
    

All Problems

All Solutions