[LeetCode] 91. Decode Ways - Java

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

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

 

Constraints:

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

---

풀이 과정

숫자로 이루어진 문자열 s가 주어지고 숫자들은 아래와 같이 알파벳으로 복호화가 가능하다고 할 때,

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

주어진 문자열을 복호화 할 수 있는 경우의 수를 구하는 문제이다.
이 때 "06" 과 "6"은 다른 문자로 판단하여 복호화가 불가능하다.

---

동적 프로그래밍을 이용하여 풀이한다.

LeetCode의 70번 Climbing Stairs 문제와 같은 맥락으로 생각을 하면 쉽다.

[LeetCode] 70. Climbing Stairs - Java

 

한 자리 혹은 두 자리를 복호화 할 수 있으므로 이전 자리 까지의 복호화 경우의 수와 두 자리 전 까지의 복호화 경우의 수를 더해주면 된다.
다만 '0'으로 시작하는 경우 복호화가 불가능한 경우이므로 이 경우에 대한 판단만 추가해준다.

---

탐색한 데이터를 저장할 배열을 선언한다.

int[] dp = new int[s.length() + 1]; // n번째 자리까지 복호화하는 경우의 수 배열

 

문자열이 '0'으로 시작하는 경우 복호화가 불가능한 문자열이므로 바로 0을 return

// 0으로 시작하면 복호화 불가능
if(s.charAt(0) == '0') return 0;

 

0번째, 1번째 자리의 경우의 수는 1로 초기화를 해준다. ( 각각 경우의 수 한가지 )

dp[0] = dp[1] = 1; // 0번째, 1번째 자리의 경우의 수는 1로 초기화

 

문자열을 순회하며 이전 자리와 두 자리 전의 경우의 수를 현재 자리의 경우에 수에 추가해준다.
이전 자리 경우의 수를 추가할 때는 현재 문자가 '0'인지를 체크한다. '0'일 경우 복호화가 불가능하므로 이 경우에는 제외한다.
두 자리 전의 경우의 수를 추가할 때는 이전 문자 + 현재 문자가 '10'과 '26'사이인지를 체크한다. 이 사이에 해당하지 않는 경우 역시 복호화가 불가능하므로 제외한다.

// 문자열 내 각 문자 탐색
// 탐색 인덱스는 0부터 시작하지만 자리수는 1부터 시작
for(int i = 1; i < s.length(); i++) {
    // 현재 문자가 복호화가 가능하면 -> '0'이 아닌 경우
    // 현재 문자까지 복호화 경우의수에
    // 이전 문자까지의 경우의 수를 더함
    if(s.charAt(i) != '0') dp[i + 1] += dp[i];

    // 이전 문자 + 현재 문자가 복호화가 가능하면 -> '26'이하인 경우
    // 현재 문자까지 복호화 경우의수에
    // 두 자리 전까지의 경우의 수를 더함
    int target = (s.charAt(i - 1) - '0') * 10 + (s.charAt(i) - '0');
    if(10 <= target && target <= 26) dp[i + 1] += dp[i - 1];
}

 

탐색이 완료된 마지막 데이터를 반환한다.

return dp[s.length()];

---

최종 코드

class Solution {
    public int numDecodings(String s) {
        int[] dp = new int[s.length() + 1]; // n번째 자리까지 복호화하는 경우의 수 배열
        
        // 0으로 시작하면 복호화 불가능
        if(s.charAt(0) == '0') return 0;
        
        dp[0] = dp[1] = 1; // 0번째, 1번째 자리의 경우의 수는 1로 초기화
        // 문자열 내 각 문자 탐색
        // 탐색 인덱스는 0부터 시작하지만 자리수는 1부터 시작
        for(int i = 1; i < s.length(); i++) {
            // 현재 문자가 복호화가 가능하면 -> '0'이 아닌 경우
            // 현재 문자까지 복호화 경우의수에
            // 이전 문자까지의 경우의 수를 더함
            if(s.charAt(i) != '0') dp[i + 1] += dp[i];
            
            // 이전 문자 + 현재 문자가 복호화가 가능하면 -> '26'이하인 경우
            // 현재 문자까지 복호화 경우의수에
            // 두 자리 전까지의 경우의 수를 더함
            int target = (s.charAt(i - 1) - '0') * 10 + (s.charAt(i) - '0');
            if(10 <= target && target <= 26) dp[i + 1] += dp[i - 1];
        }
        
        return dp[s.length()];
    }
}

---