Concise cpp solution with O(1) space and O(n) time


  • 18
    int numDecodings(string s) {
        // empty string or leading zero means no way
        if (!s.size() || s.front() == '0') return 0;
    
        // r1 and r2 store ways of the last and the last of the last
        int r1 = 1, r2 = 1;
    
        for (int i = 1; i < s.size(); i++) {
            // zero voids ways of the last because zero cannot be used separately
            if (s[i] == '0') r1 = 0;
            
            // possible two-digit letter, so new r1 is sum of both while new r2 is the old r1
            if (s[i - 1] == '1' || s[i - 1] == '2' && s[i] <= '6') {
                r1 = r2 + r1;
                r2 = r1 - r2;
            }
    
            // one-digit letter, no new way added
            else {
                r2 = r1;
            }
        }
    
        return r1;
    }

  • 5
    C

    same idea in Python:

    def numDecodings(self, s):
        if not s or s.startswith('0'):
            return 0
        wo_last, wo_last_two = 1, 1
        for i in range(1, len(s)):
            x = wo_last if s[i] != '0' else 0
            y = wo_last_two if int(s[i - 1: i + 1]) < 27 and s[i - 1] != '0' else 0
            wo_last = x + y
            wo_last_two = x
        return wo_last

Log in to reply
 

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