248. Strobogrammatic Number III - jiejackyzhang/leetcode-note GitHub Wiki

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.

##Approach 1 在"247. Strobogrammatic Number II"的基础上，先将n=low.length()到n=high.length()的strobogrammatic numbers全部求出，在一次判断，统计count。

但这会占用大量内存。

public class Solution {
    public int strobogrammaticInRange(String low, String high) {
        int count = 0;
        ArrayList<String> res = new ArrayList<String>();
        for (int i = low.length(); i <= high.length(); i++) {
            res.addAll(helper(i, i));
        }
        for (String s : res) {
            if ((s.length() == low.length() && s.compareTo(low) < 0)|| (s.length() == high.length() && s.compareTo(high) > 0)) {
                continue;
            }
            count++;
        }
        return count;
    }

    public ArrayList<String> helper(int m, int n) {
        if (m == 0) {
            return new ArrayList(Arrays.asList(""));
        } else if (m == 1) {
            return new ArrayList(Arrays.asList("0", "1", "8"));
        }
        ArrayList<String> cur = helper(m - 2, n);
        ArrayList<String> tem = new ArrayList<String>();
        for (String s : cur) {
            if (m != n) {
                tem.add("0" + s + "0");
            }
            tem.add("1" + s + "1");
            tem.add("8" + s + "8");
            tem.add("6" + s + "9");
            tem.add("9" + s + "6");
        }
        return tem;
    }
}

##Approach 2 基于第二道的基础上，不保存所有的结果，而是在递归中直接计数。 根据之前的分析，需要初始化n=0和n=1的情况，然后在其基础上进行递归，递归的长度len从low到high之间遍历。 然后我们看当前单词长度有没有达到len，如果达到了，我们首先要去掉开头是0的多位数，然后去掉长度和low相同但小于low的数，和长度和high相同但大于high的数，然后结果自增1，然后分别给当前单词左右加上那五对对称数，继续递归调用。

public class Solution {
    
    int res;

    public int strobogrammaticInRange(String low, String high) {
        res = 0;
        for (int i = low.length(); i <= high.length(); i++) {
            find(low, high, "", i);
            find(low, high, "0", i);
            find(low, high, "1", i);
            find(low, high, "8", i);
        }
        return res;
    }

    private void find(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++;
        }
        find(low, high, "0" + path + "0", len);
        find(low, high, "1" + path + "1", len);
        find(low, high, "6" + path + "9", len);
        find(low, high, "8" + path + "8", len);
        find(low, high, "9" + path + "6", len);
    }
};
⚠️ **GitHub.com Fallback** ⚠️