248. Strobogrammatic Number III

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

Given two strings low and high that represent two integers low and high where low <= high, return the number of strobogrammatic numbers in the range [low, high].

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Example 1:

Input: low = "50", high = "100"
Output: 3

Example 2:

Input: low = "0", high = "0"
Output: 1

Code

class Solution {
    public int strobogrammaticInRange(String low, String high) {
        int len1 = low.length();
        int len2 = high.length();
        
        List<String> resList = new ArrayList<>();
        
        for(int i = len1; i <= len2; i++){
            resList.addAll(helper(i, i));
        }
         int res = 0;
        
        for(String str : resList){
            if(str.length() == len1 && str.compareTo(low) < 0
              || str.length() == len2 && str.compareTo(high) > 0){
                continue;
            }
            res++;
        }
        
        return res;
    }
    
    private List<String> helper(int m, int n){
        if(m == 0) return new ArrayList<>(Arrays.asList(""));
        if(m == 1) return new ArrayList<>(Arrays.asList("0", "1", "8"));
        
        List<String> list = helper(m - 2, n);
        List<String> res = new ArrayList<>();
        
        for(String str : list){
            if(m != n){
                res.add("0" + str + "0");
            }
            
            res.add("1" + str + "1");
            res.add("6" + str + "9");
            res.add("9" + str + "6");
            res.add("8" + str + "8");
        }
        
        return res;
    }
}