91. Decode Ways

• 숫자로 표현된 알파벳 문자열을 해석할 수 있는 경우의 수를 구한다.
• 예를들어 111은 aaa 1 1 1, ak 1 11, ka 11 1 로 해석될 수 있다.
• 0의 경우 106은 1 06 과 같이 앞에 0이 오는 형태로 묶어서 해석할 수 없음에 주의한다.

• 첫번째 index부터 순차적으로 해석을 진행한다.
• 현재 자리의 숫자를 해석하고 index를 증가시킨다.
• 숫자가 0이면 잘못해석한 것이므로 경우의 수가 없는것 0 으로 한다.
• 숫자가 1이고 다음 숫자가 존재하면 현재 숫자만으로 해석한 경우 index +1 + 다음숫자까지 묶어서 해석한 경우 index +2의 수를 더한 것을 결과로 한다.
• 숫자가 2이고 다음 숫자가 0~6인 경우 현재 숫자만으로 해석한 경우 + 다음숫자까지 묶어서 해석한 경우의 수를 더한 것을 결과로 한다.
• 나머지 경우에는 현재 숫자만으로 해석한 경우의 수를 돌려준다.
• Index가 문자열 끝에 도달한 경우 해석할 수 있는 경우의 수는 한가지 뿐이므로 결과 값은 1이 된다.

• 위의 로직을 그냥 구현하게 되면 재귀호출로 인해 시간 제약에 걸릴 수 있다.
• 예를들어 1로만 이루어진 길이 인 문자열이 있을 때 재귀호출의 수는 이 되므로 문제가 될 수 있다.
• 어차피 특정 index 이후를 해석하는 경우의 수는 동일하므로 memoization을 이용하여 중복된 연산을 줄인다.

class Solution {
    public int traverse(String s, int[] dp, int index) {
        if (dp[index] != -1) return dp[index];
        int curr = s.charAt(index) - '0';
        if (curr == 0) return dp[index] = 0;
        if (curr == 1 || curr == 2) {
            if (index + 1 < s.length()) {
                int next = s.charAt(index + 1) - '0';
                boolean isValidNext =
                    curr == 1 || (curr == 2 && next <= 6);
                if (isValidNext) {
                    return dp[index] = 
                        traverse(s, dp, index + 1) + 
                        traverse(s, dp, index + 2);
                }
            }
        }
        return dp[index] = traverse(s, dp, index + 1);
    }
    
    public int numDecodings(String s) {
        int[] dp = new int[s.length() + 1];
        Arrays.fill(dp, -1);
        dp[s.length()] = 1;
        return traverse(s, dp, 0);
    }
}