[LeetCode 91] Decode Ways with JAVA

leetcode.com/problems/decode-ways/

Decode Ways - LeetCode

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).

 

class Solution {
    static int[] dp;
    public int numDecodings(String s) {
        int N = s.length();
        dp = new int[N];

        int first = s.charAt(0) - '0';
        if (first == 0) dp[0] = 0;
        else dp[0] = 1;

        int second;
        if (N >= 2){
            second = s.charAt(1) - '0';
            if (second != 0) dp[1] = dp[0];
            else if (first != 1 && first != 2) return 0;
            int number = first * 10 + second;
            if (10 <= number && number <= 26) dp[1] += 1;
        }
        else return dp[0];
        first = second;

        for (int i = 2; i < N; i++){
            second = s.charAt(i) - '0';
            if (second != 0) dp[i] = dp[i-1];
            else if (first != 1 && first != 2) return 0;
            int number = first * 10 + second;
            if (10 <= number && number <= 26) dp[i] += dp[i-2];
            first = second;
        }
        return dp[N-1];
    }
}

1. 어려웠던 점:

- DP 접근법이 너무 힘들다.

2. 알게된 점:

- DP에 더 익숙해져야 될 것 같다.

 

3. 알고리즘 풀이:

점화식은 이렇다.

first를 십의 자리, second를 일의 자리로 한다.

 

이 때, 첫 번째(0)와 두 번째 인덱스(1)는 점화식이 다르므로 따로 처리해주어야한다.

for문안에서 인덱스를 확인을 해도 되겠지만, 모든 for문마다 if문이 하나씩 늘어나므로 비효율적이다.

 

첫 번째 인덱스가 0일 경우에는 dp는 0

1일 경우 dp는 1

 

그 다음부터는

해당 인덱스의 숫자가 0이 아니면 앞의 dp와 같아진다. dp[i] = dp[i-1]

왜냐면, 0이 아닌 숫자로는 하나의 알파벳으로 디코딩할 수 있고, 그러면 앞 인덱스의 디코딩 가능 횟수를 따를 수 있기 때문이다.

 

0이라면 앞의 숫자가 1,2 가 맞는지 확인한다.

아니면 절대 디코딩될 수 없으므로 0을 리턴하고 종료한다.

이 구절이 없으면 이미 디코딩될 수 없는게 확실하지만 for loop를 다 돌아야하기 때문에 비효율적이다.

 

그 후, first * 10 + second. 즉 앞의 자리와 지금 자리의 숫자가 10 <= number <= 26에 해당하는지 확인해주고

해당하면 dp[i] += dp[i-2] 를 해준다.

두 자리 앞에 있는 경우의 수를 두 개 묶음(11)으로도 해줄 수 있기 때문이다. (하나하나 1 1 는 dp[i] = dp[i-1]에서 처리 됨)

 

이 때 인덱스가 1이라면, 그저 한 번의 경우의 수가 늘어날 뿐이므로 dp[1] = dp[0] + 1 이다.

이 것도 앞에서 따로 처리해준다.