091.Decode Ways

Posted on | In

Test cases

1
2
3
4
5
"0"
"1231230"
"0123123"
"1230123"
"12300123"

Solution 1: accepted 4ms

If the number start with 0 or has two contiguous 0, it doesn not make sense so we return 0;

  1. Base case:
    dp[0] = 1;
    dp[1] = s.charAt(0) == ‘0’? 0 : 1;

  2. Induction rule:
    dp[i] = if char is ‘0’, skip; 

    else dp += dp[i-1], if previous is not '0' and prev + currt <= 26, dp += dp[i-2];  

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int numDecodings(String s) {
    int len = s.length();
    if (len == 0) return len;
    int[] dp = new int[len + 1];
    dp[0] = 1;
    dp[1] = s.charAt(0) == '0'? 0 : 1;
    for(int i = 2; i <= len; i++) {
        int one = Integer.parseInt(s.substring(i-1, i));
        int two = Integer.parseInt(s.substring(i-2, i));
        if (one > 0 && one < 10)
            dp[i] += dp[i - 1];
        if (two > 9 && two < 27)
            dp[i] += dp[i - 2];
    }
    return dp[len];
}