Accepted Java Solution


  • 0
    W
    public class Solution {
        public int numLow=0;
        public int numHigh=0;
        public int strobogrammaticInRange(String low, String high) {
            int lenL=low.length();
            int lenH=high.length();
            if(low.startsWith("-")) low="";
            if(high.startsWith("-") || lenL>lenH) return 0;
            Map<Integer, Integer> map=new HashMap<Integer, Integer>();
            map.put(0, 0); map.put(1, 3);map.put(2, 4); map.put(3, 12); map.put(4, 20);
            // when it is over 4, F[i]=F[i-2]*(F[2]+1) because it need also count "00" which is not count by F[2]
            for(int i=5;i<=lenH;i++)
                map.put(i, 5*map.get(i-2));
            getCountHelper(lenL, "", low, true);
            getCountHelper(lenH, "", high, false);
            int count=0;
            for(int i=lenL;i<=lenH-1;i++)
                count+=map.get(i);
            return Math.max(0, count+numHigh-numLow);
        }
        public void getCountHelper(int n, String currentStr, String str, boolean isLow){
            int len=currentStr.length();
            if(len==n){
                if(currentStr.compareTo(str)<0){
                    if(isLow) numLow++;
                    else numHigh++;
                }else if(currentStr.equals(str) && !isLow) numHigh++;
                return;
            }
            if(len>n) return;
            if(len==0){
                getCountHelper(n, "0", str, isLow);
                getCountHelper(n, "1", str, isLow);
                getCountHelper(n, "8", str, isLow);
            }
            if(len!=n-2) getCountHelper(n, "0"+currentStr+"0", str, isLow);
            getCountHelper(n, "1"+currentStr+"1", str, isLow);
            getCountHelper(n, "6"+currentStr+"9", str, isLow);
            getCountHelper(n, "9"+currentStr+"6", str, isLow);
            getCountHelper(n, "8"+currentStr+"8", str, isLow);
        }
    }

Log in to reply
 

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