c++ 3 lines dfs + dp


  • 0
    L
    int numDecodings(const string& s) {
        vector<int> hm(s.size()+1, -1);
        function<int(int)> dfs = [&](int i){ return hm[i] = (hm[i]!=-1 ? hm[i] : (s[i]=='0' ? 0 : (dfs(i+1) + ((i<s.size()-1 && (s[i]=='1' || (s[i]=='2'&&s[i+1]<='6'))) ? dfs(i+2) : 0)))); };
        return s.empty() ? 0 :  (hm[s.size()] = 1, dfs(0));

Log in to reply
 

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