[LeetCode] 91. Decode Ways

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

Decode Ways - LeetCode

leetcode - Decode Ways

문제 유형 : 다이나믹 프로그래밍

문제 난이도 : Medium

 

문제

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.

 

문자 A-Z는 각각 1 ~ 26으로 매핑될 수 있습니다.

 

암호화된 문자를 해독하려면, 모든 숫자들이 각각 나뉘어져서 역순으로 매핑되어서 문자로 나타탭니다.

예를 들어, 11106은 

• AAJF(1 1 10 6)
• KJK(11 10 6)

의 2가지로 나뉠 수 있습니다.

앞에 0이 붙는 것은 두 자리 수로 인정하지 않습니다.

 

정수문자열 s가 주어집니다. 해독할 수 있는 모든 경우의 수를 구하시오.

테스트 케이스는 32비트정수로 반환될 수 있도록 구성되어 있습니다.

 

 

풀이

LeetCode 70번문제와 유사하다.

 

정수를 1개 또는 2개를 읽을 수 있으니, 한칸 전과 두칸 전의 경우의 수를 각각 읽어서 누적하면 된다.

단, 1개씩 읽는 경우 0이면 한칸 전의 값에서 가져올 수 없다.

또한, 2개씩 읽는 경우에서 10 ~ 26이 아닌 경우 역시 두칸 앞의 경우의 수를 더할 수 없다.

이 예외상황만 처리해주면 된다.

 

코드

C++

class Solution {
public:
    int numDecodings(string s) {
        const int n = s.size();
        if(n == 0 || s[0] == '0') return 0;
        vector<int> dp(n+1, 0);
        dp[0] = 1;
        dp[1] = 1;

        for(int i = 2; i <= n; i++) {
            auto oneDigit = s[i-1];
            auto twoDigits = s.substr(i-2, 2);

            if(oneDigit != '0')
                dp[i] += dp[i-1];
            if(stoi(twoDigits) >= 10 && stoi(twoDigits) <= 26)
                dp[i] += dp[i-2];
        }
        return dp[n];
    }
};