DP solution with O(n) time using C++


  • 0
    M
    int numDecodings(string s) {
            int len = s.size(), *ans = new int[len]();
            for(int i=0; i<len; i++){
                // Check one character
                if('1'<=s[i] && s[i]<='9')              // 1 ~ 9
                    if(i==0) 
                        ans[i] = 1;
                    else 
                        ans[i] = ans[i-1];
                // Check two characters
                if((s[i-1]=='1' && ('0' <= s[i] && s[i] <= '9')) ||     // 10 ~ 19
                   (s[i-1]=='2' && ('0' <= s[i] && s[i] <= '6'))){      // 20 ~ 26
                    if(i>=2) 
                        ans[i] += ans[i-2];
                    else 
                        ans[i]++;
                }
            }
            return ans[len-1];
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.