easy understanding DP solution, process the string from index 0 to N-1


  • 0

    the idea is very straightforward, when processing the ith character, you can decode it single or bind with its previous character, just be careful for some edge cases as the comments below.

    public class Solution {
        public int numDecodings(String s) {
            int n = s.length();
            if(n == 0) return 0;
            int[] dp = new int[n+1];
            dp[0] = s.charAt(0) == '0' ? 0 : 1;//case 1: "", 1 way; case 2: "0",  0 way;
            dp[1] = s.charAt(0) == '0' ? 0 : 1;//case 1: "1"~"9", 1 way; case 2: "0",  0 way;
            for(int i = 2; i < dp.length; i ++){
                int numi = s.charAt(i-1) - '0';
                int numpre = s.charAt(i-2) - '0';
                if(numi == 0){
                    int sum = numpre*10 + numi;
                    if(sum == 10 || sum == 20) {//only 10 and 20 match the mapping
                        dp[i] += dp[i-2];
                    }
                }else if(numi > 0 && numi <= 9){
                    if(numpre != 0 && numpre*10 + numi <= 26){ //the mapping range from 1~26
                        dp[i] += dp[i-2];
                    }
                    dp[i] += dp[i-1];
                }
            }
            return dp[n];
        }
    }
    

Log in to reply
 

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