[leetcode #91] Decode Ways

Problem

A message containing letters from A-Z can be encoded into numbers using the following mapping:

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

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:

・ "AAJF" with the grouping (1 1 10 6)
・ "KJF" with the grouping (11 10 6)

Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

Given a string s containing only digits, return the number of ways to decode it.

The answer is guaranteed to fit 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 = "0"
Output: 0
Explanation: There is no character that is mapped to a number starting with 0.
The only valid mappings with 0 are 'J' -> "10" and 'T' -> "20", neither of which start with 0.
Hence, there are no valid ways to decode this since all digits need to be mapped.

Example 4:

Input: s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06").

Constraints:

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

Idea

이전에 Decode Ways II를 푼 적이 있어서 그런지 쉽게 풀었다. 알파벳 순서대로 1~26까지 match가 되는데 숫자로 encoding된 문자열을 다시 알파벳으로 바꿀 때 가능한 알파벳 문자열 수가 몇 개인지 세는 문제다. 주의해야 할 점은 0과 두 자리 숫자를 처리하는 것이다.

문자열을 앞에서부터 탐색해 해당 문자열에서 decoding 가능한 수를 dp에 저장한다. 현재 탐색하고 있는 문자의 index가 i고 문자가 0이 아닐 경우, (i-1)번째 index에서 가능한 문자열의 수대로 i번째에서 decoding이 가능하다. 앞의 수가 1일때, 그리고 앞의 수가 2고 현재 수가 6보다 작거나 같은 경우 (<=26) (i-2)번째 index에서 가능한 문자열의 수대로 i번째에서 decoding이 가능하다.

알고리즘은 다음과 같다.

1. 문자열이 0으로 시작하면 0을 리턴한다.
2. 0번째와 1번째 문자가 주어졌을 때 decoding 가능한 수를 1로 설정한다.
3. 2번째 문자 (ith index)부터 탐색을 시작한다.
   a. 바로 앞의 문자가 0이 아닐 경우 (i-1)th index에서 decoding가능한 수를 더한다.
   b. 현재 문자가 0이고 앞의 문자가 1이나 2가 아니면 0을 리턴한다.
   c. 앞의 문자가 1이거나, 앞의 문자가 2고 현재 문자가 6보다 작거나 같을 경우 (i-2)th index에서 decoding 가능한 수를 더한다.
4. n번째 문자열에서 decoding 가능한 수를 리턴한다.

Solution

class Solution {
    int[] dp;

    public int numDecodings(String s) {
    	dp = new int[s.length()+1];

        if (s.startsWith("0"))
            return 0;
        dp[0] = 1;
        dp[1] = 1;

        for (int i=2; i <= s.length(); i++) {
            if (s.charAt(i-1) != '0')
                dp[i] += dp[i-1];
            else {
                if (s.charAt(i-2) != '1' && s.charAt(i-2) != '2')
                    return 0;
            }
            if (s.charAt(i-2) == '1' || (s.charAt(i-2) == '2' && s.charAt(i-1) <= '6'))
                dp[i] += dp[i-2];
        }

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

Reference

https://leetcode.com/problems/decode-ways/