Java dp solution


  • 0
    S
    public class Solution {
        public int numDecodings(String s) {
            int len = s.length(), i , j;
            
            if(len == 0)
                return 0;
            
            int[] count = new int[len];
            
            if(s.charAt(len - 1) == '0')
                count[len - 1] = 0;
            else
                count[len - 1] = 1;
                
            if(len == 1)
                return count[0];
        
            if (s.charAt(0) == '0')
                return 0;
            
            if(s.charAt(len - 2) == '1') {
                count[len - 2] = count[len - 1] + 1;
            } else if(s.charAt(len - 2) == '2') {
                if(s.charAt(len - 1) - '0' > 6) {
                    count[len - 2] = 1;
                } else if(s.charAt(len - 1) == '0') 
                    count[len - 2] = 1;
                else
                    count[len - 2] = 2;
            } else {
                count[len - 2] = count[len - 1];
            }
            
            if(len == 2)
                return count[0];
            
            for (i = len - 3;i>=0;i--) {
                if(s.charAt(i) == '1') {
                    if(s.charAt(i + 1) == '0') {
                        count[i] = count[i + 2];
                    } else {
                        count[i] = count[i + 1] + count[i + 2];
                    }
                } else if(s.charAt(i) == '2') {
                    if(s.charAt(i + 1) - '0' > 6 || s.charAt(i + 1) == '0')
                        count[i] = count[i + 1];
                    else
                        count[i] = count[i + 1] + count[i + 2];
                        
                } else {
                    if(s.charAt(i + 1) == '0')
                        return 0;
                    else
                        count[i] = count[i + 1];
                }
            }
            
            return count[0];
        }
    }

Log in to reply
 

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