[LeetCode] 91. Decode Ways

Posted on | In

Problem

A message containing letters from A-Z is being encoded to numbers using the following mapping:

1
2
3
4
'A' -> 1
'B' -> 2
...
'Z' -> 26

Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

1
2
3
Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2:

1
2
3
Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Explanation

  1. We can use dynamic programming to solve this problem.

  2. Dynamic state is a one dimensional array, dp[s.length()+1], and its i index element is the decode ways of the substring choosing the first i character. For example, let input string s=123, then dp[1] is the decode way of 1; dp[2] is the decode way of 12; dp[3] is the decode way of 123;

  3. Dynamic init is dp[1]=1, dp[0]=1 because later we want the dynamic function to be dp[i] = dp[i-1] + dp[i-2], so dp[2] = dp[1] + dp[0], so we need to set dp[0] to some value, dp[0] is 1 because in general case, for example string s="12", we know the decode way is 2; s="1", we know the decode way is 1, so we set dp[1]=1, so dp[0]=1.

  4. Dynamic function in general case is dp[i] = dp[i-1] + dp[i-2]. For example, s = "123", if i is iterating at character 3, then we can think of 3 as a group, 12 as another group, in this case s = "123" its decode way is the same the decode way of s=12, in other word, dp[i] = dp[i-1]. Beside this, we can think of 23 as a group, 1 as another group, in this case, its decode way is the same when s=1, in other word, dp[i] = dp[i-2].

  5. There are some special case of the above dynamic function. If the string is “120”, the current iterated element is 0, then we cannot think of 0 as a group, we need to consider “20” as a group, 1 as another group, so dp[i] = dp[i-2]. Also, if the string is “130” or “100”, then we cannot think of “0”, “30”, or “00” as a group, there is actually no way to decode such string. One more special case is when s=103, we can think of 3 as a group and 10 as another group, so dp[i]=dp[i-1], but we cannot think of 03 as group, so we cannot use dp[i]=dp[i-2].

  6. Dynamic result is dp[s.length()], which means return the decode way when we choose all the elements.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int numDecodings(String s) {
        if (s.charAt(0) == '0') return 0;
        int[] dp = new int[s.length()+1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= s.length(); i++) {
            if (s.charAt(i-1) == '0') {
                if (s.charAt(i-2) != '1' && s.charAt(i-2) != '2') {
                    return 0;
                }
                dp[i] = dp[i-2];
            } else {
                if (s.charAt(i-2) == '0' || Integer.valueOf(s.substring(i-2, i)) > 26) {
                    dp[i] = dp[i-1];
                } else {
                    dp[i] = dp[i-1] + dp[i-2];
                }
            }

        }

        return dp[s.length()];
    }
}