[c++/LeetCode-DP] 91. Decode Ways (w/ DP 풀이 전략)

 

 

 

난이도: Medium

키워드: DP

 

 

📍 문제

 

알파벳 A-Z의 문자로 이루어진 메시지는 다음 매핑을 사용하여 숫자로 인코딩될 수 있습니다:

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

 

인코딩된 메시지를 디코딩하려면, 모든 숫자를 그룹화하고 위의 매핑을 반대로 사용하여 다시 문자로 매핑해야 합니다 (여러 방법이 있을 수 있음). 예를 들어, "11106"은 다음과 같이 매핑될 수 있습니다:

(1 1 10 6)을 그룹화하여 "AAJF"
(11 10 6)을 그룹화하여 "KJF"
(1 11 06)을 그룹화하는 것은 "06"을 'F'로 매핑할 수 없으므로 잘못된 것임에 유의하세요.

숫자만 포함하는 문자열 s가 주어졌을 때, 이를 디코딩하는 방법의 수를 반환하세요.
테스트 케이스는 답이 32비트 정수에 맞도록 생성됩니다.

 

문제 원문: https://leetcode.com/problems/decode-ways/description/

 

📍 입출력 예시

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

 

 

 

📍 문제 풀이

 

해당 문제는 string의 n 번째 숫자까지의 decoding 가능한 경우의 수를 구하는 데에 앞선 n-1, n-2 까지의  경우의 수를 가지고 구할 수 있다는 점에서 dynamic programming (DP)를 사용해서 문제를 풀 수 있다.

 

예를 들어, a[n]을 n 번째 자리의 string 까지의 decoding 가능한 경우의 수라고 정의한다고 하면 a[n]은 조건부적으로 a[n-2] + a[n-1]로 구할 수 있다. 이 때, 각 조건은 다음과 같다. code[n-1], code[n]으로 두 자리 코드를 만들 수 있다고한다면 n-2까지만으로 만들 수 있는 코드 경우의  수를 그대로 가져올 수 있다. 또 한편으로 code[n]이 0이 아니라면 한 자리 수만으로도 코드가 될 수 있기 때문에  a[n-1] 까지 만들 수 있는 코두드 경우의 수를 그대로 가져올 수  있다.

 

 

 

이를 코드로 옮기면 다음과 같다.

 

Runtime 0 ms: Beats 100.00 % of users with c++

Memory: 7.37 MB Beats 96.92 % of users with c++

#define num(x) (int(x)-48)
#define nums(x,y) num(x)*10+num(y)

class Solution {
public:
    int numDecodings(string s) {

        const int N = s.size();
        vector<int> a(N, 0);

        if(num(s[0])== 0)
            return 0;
        if(N == 1)
            return 1;

        // baseline initialization
        // a[0]
        a[0] = 1;
        // a[1]
        if(num(s[1]) == 0)
            a[1] = ((nums(s[0],s[1]) >= 10) &&  (nums(s[0],s[1])<= 26))? a[0] : 0;
        else
            a[1] = ((nums(s[0],s[1]) >= 10) &&  (nums(s[0],s[1])<= 26))? a[0] + 1: a[0];

        // a[n]
        for(int n = 2; n < N; ++n){
            a[n] = a[n-2] * (int)((nums(s[n-1],s[n]) >= 10 && nums(s[n-1],s[n]) <= 26) && num(s[n-1] != 0)) + a[n-1] * (int)(num(s[n]) != 0);
        }

        return a[N-1];
        
    }
};