[리트코드] 0711

 

https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/609/week-2-july-8th-july-14th/3809/

 

정규식 해석? 비슷한 문제였다. A=1, Z=26으로 해석할 수 있을 때, 문자열 s가 주어지고, s를 해석할 수 있는 가짓수를 묻는 문제였다.

예를들어, 123은 (1,2,3), (12,3), (1,23)의 3가지 방법으로 해석할 수 있다. 특이한 점은 1~9로 모두 해석가능한 * 문자도 s 에 들어있다는 것이다.

DP를 사용해 배열 끝쪽부터 보면서

1. i번째에서 문자 1개로 읽을 수 있는 경우(1<= s[i] <= 9)에는 dp[i] = dp[i+1]

2. i번째에서 i와 i+1을 보고 문자 두개로 읽을 수 있는 경우에는 dp[i] = dp[i+2]를 하면서 구했다. 

* 문자의 해석을 신경써줘야해서 힘들었다

class Solution {
public:
    int numDecodings(string s) {
        long long MOD = 1000000007;
        long long dp[100001] = {0,};
        int n = s.size();
        long long cnt=0;
        
        dp[n] = 1;
        switch(s[n-1]){
            case '0':
                dp[n-1] = 0;
                break;
            case '*':
                dp[n-1] = 9;
                break;
            default:
                dp[n-1] = 1;
                break;
            
        }
        
        for(int i=n-2; i>=0; i--){
            if('1' <= s[i] && s[i] <= '9')
                dp[i] = (dp[i] + dp[i+1])%MOD;
            else if(s[i] == '*')
                dp[i] = (dp[i] + (9*dp[i+1])%MOD)%MOD;
            
            if(s[i]=='1'){
                if(s[i+1] == '*')
                    dp[i] = (dp[i] + (9*dp[i+2])%MOD)%MOD;
                else
                    dp[i] = (dp[i] + dp[i+2])%MOD;
            }
            else if(s[i] =='2'){
                if('0' <= s[i+1] && s[i+1] <= '6')
                    dp[i] = (dp[i] + dp[i+2])%MOD;
                else if(s[i+1] == '*')
                    dp[i] = (dp[i] + (6*dp[i+2])%MOD)%MOD;
            }
            else if(s[i] =='*'){
                if(s[i+1] == '*'){
                    dp[i] = (dp[i] + (9*dp[i+2])%MOD)%MOD;
                    dp[i] = (dp[i] + (6*dp[i+2])%MOD)%MOD;
                }
                else{
                    dp[i] = (dp[i] + dp[i+2])%MOD;
                    if('0' <= s[i+1] && s[i+1] <= '6')
                        dp[i] = (dp[i] + dp[i+2])%MOD;
                }
            }
        }
        return dp[0];
    }
};