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);
        }
    }
}

All Problems

All Solutions