my method using DP, not very fast.


  • 0

    In my code, I use dp to calculate the number between lowlen and highlen. The dp array, contains a Pair object.
    For example: when len = 2 , dp[1] = (4,1) .

    Because when len = 2, there are five combinations: "00" , "11" , "69" , "88" , "96". We keep the last four results as the final result of this length. But even though "00" is not a result for this length, it can also contributes to the next length, so we should keep it.

    But for the length == low.length() and length == high.length(), we should find all of the results and compare to the bound using "Strobogrammatic Number II".

    My code is not very fast(98ms), just to make a new thought. Hopping to help you.

    public class Solution {
        public int strobogrammaticInRange(String low, String high) {
            if(low.length() > high.length()) return 0;
            int len = high.length();
            int res = 0;
            if(len >= 2) {
                Pair[] dp = new Pair[len];
                dp[0] = new Pair(3 , 0);
                dp[1] = new Pair(4 , 1);
                for(int i = 2 ; i < len ; i++) {
                    int l = 4*(dp[i-2].l + dp[i-2].r);
                    int r = dp[i-2].l + dp[i-2].r;
                    dp[i] = new Pair(l , r);
                }
                int lowlen = low.length();
                int highlen = high.length();
                for(int i = lowlen ; i < highlen-1 ; i++) {
                    res += dp[i].l;
                }
            }
            int count = 0;
            List<String> lowlist = dfshelper(low.length() , low.length());
            List<String> highlist = dfshelper(high.length() , high.length());
            if(low.length() == high.length()) {
                for(int i = 0 ; i < lowlist.size() ; i++) {
                    if(low.compareTo(lowlist.get(i)) <= 0 && high.compareTo(highlist.get(i)) >= 0) {
                        count++;
                    }
                }
            }else {
                for(int i = 0 ; i < lowlist.size() ; i++) {
                    if(low.compareTo(lowlist.get(i)) <= 0) {
                        count++;
                    }
                }
                for(int i = 0 ; i < highlist.size() ; i++) {
                    if(high.compareTo(highlist.get(i)) >= 0) {
                        count++;
                    }
                }
            }
            return count + res;
        }
    
        protected List<String> dfshelper(int n , int m) {
            if(n == 0) return new ArrayList<String>(Arrays.asList(""));
            if(n == 1) return new ArrayList<String>(Arrays.asList("0" , "1" , "8"));
            List<String> res = new ArrayList<String>();
            List<String> temp = dfshelper(n-2 , m);
            for(int i = 0 ; i < temp.size() ; i++) {
                if(n != m) res.add("0" + temp.get(i) + "0");
                res.add("1" + temp.get(i) + "1");
                res.add("6" + temp.get(i) + "9");
                res.add("8" + temp.get(i) + "8");
                res.add("9" + temp.get(i) + "6");
            }
            return res;
        }
        
        public class Pair {
            int l;
            int r;
            public Pair(int l , int r) {
                this.l = l;
                this.r = r;
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.