Leetcode - 91. Decode Ways

문제

숫자로 이루어진 문자열이 주어진다. 각 수들이 문자로 decode된다면 총 몇가지 경우의 수 가 존재하는가?

"AAJF" with the grouping (1 1 10 6)
"KJF" with the grouping (11 10 6)

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

Input: s = "226"
Output: 3
Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

해결

f(n) = f(n + 1) + f(n + 2) 라는 재귀적인 구조는 쉽게 파악할수 있었는데, base case 종료조건을 자꾸 틀려서 애먹음.
추가로 memoization 을 안하면 TLE 발생.

class Solution {
    unordered_map<string, bool> map;
    unordered_map<int, int> mem;
    
    int recur(string s, int cur) {
        if (mem.find(cur) != mem.end())
            return mem[cur];
        if (cur == s.length()) // <- 종료조건 마지막 바로 다음 index에 도달했다면 decode에 성공했다는 뜻.
            return 1;
        if (cur > s.length() || s[cur] == '0')
            return 0;
        int ret = 0;
        if (map.find(s.substr(cur, 1)) != map.end())
            ret += recur(s, cur + 1); 
        if (map.find(s.substr(cur, 2)) != map.end())
            ret += recur(s, cur + 2); 
        mem[cur] = ret;
        return ret;
    }
public:
    int numDecodings(string s) {
        for (int i = 1; i <= 26; i++)
            map[std::to_string(i)] = true;
        return recur(s, 0);
    }
};

아래는 221016 다시 풀어본 더 효율적 풀이, memoization용으로만 해시테이블이 추가로 필요.

class Solution {
public:
    unordered_map<int, int> mem;
    
    /* f(i) = f(i+1) + f(i+2) */
    int recur(string s, int cur) {
        if (mem.find(cur) != mem.end())
            return mem[cur];
        if (cur == s.length())
            return 1;
        if (cur > s.length() || s[cur] == '0')
            return 0;
        
        int ret = recur(s, cur + 1);
        if (stoi(s.substr(cur, 2)) <= 26)
            ret += recur(s, cur + 2);
        mem[cur] = ret;
        return ret;
    }
    int numDecodings(string s) {
        return recur(s, 0);
    }
};