Leetcode 91. Decode Ways

tags: Leetcode(C++)

題目 : https://leetcode.com/problems/decode-ways/ 。

想法 :

​​​​類似爬梯子的DP，但是有特殊條件要處理。
​​​​1. 如果是0開頭、0前面不是接1 or 2就一定是False。
​​​​2. 能往前算2格的狀態只有26以內，所以要往前看確認是狀態轉移1格還是2格，注意前方是0，所以我先預處理把10跟20標成XX。

時間複雜度 : O(n)。

程式碼 :

class Solution {
public:
    int numDecodings(string s) {
        int l=s.size(), sum[110]={0}, ok=1;
        
        if(s[0] == '0') return 0;
        for(int i=1 ; i<l ; i++){
            if(s[i] == '0'){
                if(s[i-1] == '1' || s[i-1] == '2'){
                    s[i-1]='X'; s[i]='X';
                }
                else{
                    ok=0; break;
                }
            }
        }
        
        sum[0]=1;
        if(s[0] == '1' && s[1]-'0' > 0 && s[1]-'0' <= 9) sum[1]=2;
        else if(s[0] == '2' && s[1]-'0' <= 6) sum[1]=2;
        else if(s[0] == 'X' && s[1] == 'X') sum[0]=sum[1]=1;
        else if(s[1] == 'X' && s[2] == 'X') sum[1]=sum[2]=1;
        else sum[1]=1;
        
        for(int i=2 ; i<l&&ok ; i++){
            if(s[i] == 'X'){
                i++;
                sum[i]+=sum[i-2];
            }
            else{
                sum[i]+=sum[i-1];
                if(s[i-1] == '1') sum[i]+=sum[i-2];
                if(s[i-1] == '2' && (s[i]-'0' <= 6)) sum[i]+=sum[i-2];   
            }
        }
        
        /*for(int i=0 ; i<l ; i++){
            cout << sum[i];
        }*/
        
        if(!ok) return 0;
        return sum[l-1];
    }
};