Share my C++ solution,O(n) time and O(1) space,easy to understand


  • 0
    V
    class Solution {
    public:
        int numDecodings(string s) {
            int len = s.length();
            if (len == 0 || s[0] == '0')
                return 0;
            
            for (int i = 1; i < len; i++)
            {   
                if (s[i] == '0' && s[i-1] != '1' && s[i-1] != '2')
                    return 0;
            }
            
            int dp_pre_pre = 1;//s[-1]
            int dp_pre = 1;//s[0]
            int dp_cur = dp_pre;
            
            for (int i = 1; i < len; i++)
            {
                dp_cur = 0;
                
                if (s[i] != '0')
                    dp_cur += dp_pre;
                
                if (s[i-1] == '1' || (s[i-1] == '2' && s[i] <= '6'))
                    dp_cur += dp_pre_pre;
                
                dp_pre_pre = dp_pre;  
                dp_pre = dp_cur;
            }
            
            return dp_cur;
        }
    };

Log in to reply
 

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