C++ 7 lines 0ms clean DP solution


  • 3
      int numDecodings(string s) {
            // pre: previous digit; ways0: ways of i - 2; ways1: ways of i - 1
            int pre = 0, ways0 = 0, ways1 = s.empty() ? 0 : 1;
            
            for (char c : s) {
                int cur = c - '0';  // current digit
                int ways = (cur != 0 ? ways1 : 0) + (pre != 0 && (pre * 10 + cur) <= 26 ? ways0 : 0);
                ways0 = ways1, ways1 = ways, pre = cur;     // update ways0, ways1 and pre
            }
            
            return ways1;
        }
    

Log in to reply
 

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