Java DP Solution beats 93% (1ms)


  • 0
    M
    public class Solution {
        public int numDecodings(String s) {
            int n = s.length();
            if (n==0)   return 0;
            if (s.equals("0"))   return 0;
            if (n==1)   return 1;
            int[] dp = new int[n+1];
            dp[0] = 1;
            dp[1] = 1;
            for (int i=2; i<=n; i++)
                dp[i] = dp[i-1] + dp[i-2];
            int prod = 1;
            int len = 0;
            
            char[] k = s.toCharArray();
            
            for (int i=0; i<n; i++) {
                len++;
                if (k[i]-'0' >= 3) {
                    prod *= dp[len];
                    len = 0;
                }
                else if (k[i] == '0') {
                    if (len-2 < 0)  return 0;
                    prod *= dp[len-2];
                    len = 0;
                }
                else if (i!=n-1 && k[i]=='2' && k[i+1]-'0' >= 7) {
                    prod *= dp[len];
                    len = 0;
                }
                else if (i==n-1) {
                    prod *= dp[len];
                }
            }
            
            return prod;
        }
    }
    

Log in to reply
 

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