[DP] 91. Decode Ways

문제

You have intercepted a secret message encoded as a string of numbers. The message is decoded via the following mapping:

"1" -> 'A' "2" -> 'B' ... "25" -> 'Y' "26" -> 'Z'

However, while decoding the message, you realize that there are many different ways you can decode the message because some codes are contained in other codes ("2" and "5" vs "25").

For example, "11106" can be decoded into:

• "AAJF" with the grouping (1, 1, 10, 6)
• "KJF" with the grouping (11, 10, 6)
• The grouping (1, 11, 06) is invalid because "06" is not a valid code (only "6" is valid).

Note: there may be strings that are impossible to decode.

Given a string s containing only digits, return the number of ways to decode it. If the entire string cannot be decoded in any valid way, return 0.

The test cases are generated so that the answer fits in a 32-bit integer.

Example 1:

Input: s = "12"

Output: 2

Explanation:

"12" could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: s = "226"

Output: 3

Explanation:

"226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Example 3:

Input: s = "06"

Output: 0

Explanation:

"06" cannot be mapped to "F" because of the leading zero ("6" is different from "06"). In this case, the string is not a valid encoding, so return 0.

Constraints:

• 1 <= s.length <= 100
• s contains only digits and may contain leading zero(s).

Solution

class Solution {
    public int numDecodings(String s) {
        if (s.charAt(0) == '0') {
            return 0;
        }

        int n = s.length();
        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            int one = Character.getNumericValue(s.charAt(i - 1));
            int two = Integer.parseInt(s.substring(i - 2, i));

            if (1 <= one && one <= 9) {
                dp[i] = dp[i - 1];
            }
            if (10 <= two && two <= 26) {
                dp[i] += dp[i - 2];
            }
        }

        return dp[n];        
    }
}

회고

이 문제에서, dp[i]를 정의하고 계산하는 과정에서 중요한 점은 dp[i-1]과 dp[i-2]의 경우의 수가 서로 겹치지 않는다는 사실이다. 이 문제에서 dp[i]를 계산하는 핵심 원리다. 참고로, dp[i]는 문자열 s의 첫 i개의 문자로 이루어진 부분 문자열을 디코딩할 수 있는 방법의 수를 나타낸다.

• 만약 s[i]가 1에서 9 사이의 유효한 한 자리 숫자라면, 한 자리만 해석하는 방법으로 dp[i-1]의 경우의 수를 이어받는다.
• 또한, 문자열 s[i-1] ~ s[i]가 10에서 26 사이의 유효한 두 자리 숫자라면, 두 자리 숫자를 해석하는 방법으로 dp[i-2]의 경우의 수를 이어받는다.

추가로, 빈 문자열 ""은 복호화 가능한 경우가 하나뿐("")이므로 dp[0] = 1로 정의한다. DP 문제를 해결할 때는 초기화를 어떻게 설정할지 항상 염두에 두자.