Very Very Concise C++ solution


  • 3
    int numDecodings(string s) {
        if (s.empty()) return 0;
        int a = 1, b = 0;
        for (int i = s.size() - 1; i >= 0; i--) {
            int temp = a;
            a = s[i] == '0' ? 0 : a + (stoi(s.substr(i, 2)) <= 26 ? b : 0);
            b = temp;
        }
        return a;
    }
    

  • 0

    @zyoppy008 Great concise solution! To make it more readable, I separate condition "?" in separate lines with comments, and renamed some variables to be more descriptive.

        int numDecodings(string s) {
            int n = s.length(); if (n == 0) return 0;
            int cur = 1;  // num of decode ways of s.substr(i+1)
            int prev = 0; // num of decode ways of s.substr(i+2)
            for (int i = n-1; i >= 0; i--) {
              int cur_copy = cur;
              // update cur to store num of decode ways of s.substr(i)
              if (s[i] == '0') cur = 0; // cannot decode string with leading '0'
              // leading two chars can be interpreted togather or separately
              else if (stoi(s.substr(i,2)) <= 26) cur += prev; 
              // else: leading char has to be interpreted separately 
              //       so s.substr(i) has same decode ways as s.substr(i+1)
              
              // update prev to store num of decode ways of s.substr(i+1)
              prev = cur_copy;
            }
            return cur;
        }
    

  • 0
    F

    Great solution and thanks @zyoppy008 for the comments!


Log in to reply
 

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