JAVA DP solution beat 91%


  • 0
    T
    public int numDecodings(String s) {
            if( s.compareTo("") == 0) return 0;
             char[] ch=s.toCharArray();
            int[] ways = new int[s.length()+1];
            ways[ch.length] = 1;//sweep the ch from the end of the string
            int prev = -1;
            for (int i = ch.length-1;i >= 0;i--) {
                int cur = ch[i]-48;
                if(cur+prev==0&&prev!=-1) return 0;//when it comes to the string like "00",it will return 0.
                if (cur != 0) {
                    ways[i] = (prev !=-1 && cur*10+prev<=26) ? ways[i+2]+ways[i+1] : ways[i+1];
                }
                prev = cur;
            }
            
            return ways[0];
        }
    

Log in to reply
 

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