LeetCode (C/C++, Java) 91. Decode Ways

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

 

---

풀이

재귀로 풀릴 것 같아 도전했으나 답이 나오지 않아 답지를 봤다.

먼저 현재 값이 0이 아니라면 경우의 수 1개를 더한다.

만약 현재 값이 1이거나 바로 뒤의 숫자 하나까지 더해 'z'의 값인 26 이하(두 자릿수가 가능한 경우)라면 해당 경의 수를 하나 더 더해주었다.

이런 방식으로 뒤에서부터 탐색하며 처음 위치에까지 경우의 수를 구해 총 가짓수를 구했다.

---

C/C++ 코드

class Solution {
public:
    int numDecodings(string s) {
        int len = s.size();
        int dp[101] = {0, };

        dp[len] = 1;
        for (int i = len - 1; i >= 0; i--) {
            if (s[i] != '0') {
                dp[i] = dp[i + 1];
                if (i < len - 1 && (s[i] == '1' || s[i] == '2' && s[i] + 1 < '7'))
                    dp[i] += dp[i + 2];
            }
        }
        return dp[0];
    }
};

 

Java 코드

class Solution {
    public int numDecodings(String s) {
        int len = s.length();

        int[] dp = new int[len + 1];
        dp[len] = 1;
        for (int i = len - 1; i >= 0; i--) {
            if (s.charAt(i) != '0') {
                dp[i] = dp[i + 1];
                if (i < len - 1 && (s.charAt(i) == '1' || s.charAt(i) == '2' && s.charAt(i + 1) < '7'))
                    dp[i] += dp[i + 2];
            }
        }
        return dp[0];
    }
}