5ms c++ solution, DP, O(n), traversed the string from right to left.


  • 0

    This is my 5ms DP solution, in the code, preRes is the decode ways of substring from index i+1 to the end, and res is the decode ways of substring from index i to the end.

    For example, if s="180512", when i=4, preRes is the decode ways of “2”, res is the decode ways of "12", then i=3, preRes is the decode ways of "12", res is the decode ways of "512", ...

    class Solution {
    public:
        int numDecodings(std::string s) {
    		if (s.empty())
    			return 0;
    		int len = static_cast<int>(s.size());
    		int preRes = 1, res = 0, tmp;
    		if (s[len - 1] != '0')
    			res = 1;
    		for (int i = len - 2; i >= 0; --i) {
    			tmp = preRes;
    			preRes = res;
    			if (s[i] == '0')
    				res = 0;
    			else if (s[i] == '1' || (s[i] == '2' && s[i + 1] < '7'))
    				res += tmp;
    			if (!res && !preRes)
    				return 0;
    		}
    		return res;
        }
    };

Log in to reply
 

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