[LeetCode]Decode Ways

很明显递归思路的题，用f(s)代表num of ways to decode string s，s[i:]代表从i开始到结尾的substring, s[:i]代表从[0, i)的substring, 那么有以下公式：

• f(s) = f(s[1:]) + f(s[2:]), if s[0] != 0, and s[:2] <= 26
• f(s) = f(s[1:]), if s[0] != 0, and s[:2] > 26
• f(s) = 0, if s[0] == 0

更具以上递归的公式我们横很容易就可以写出代码，但是有很多的重复的计算，无法过很长的test case。显然我们需要用dp来做优化，那么dp递推公式和上面是一样的。时间复杂度O(n)，空间复杂度O(n)，代码如下：

	class Solution {
	public:
	int numDecodings(string s) {
	int len = s.size();
	if(!len)return 0;
	vector<int> dp(len + 1, 0);
	dp[len] = 1;
	dp[len - 1] = s[len - 1] == '0'? 0: 1;
	for(int i = len - 2; i >= 0; --i)
	{
	if(s[i] == '0')
	dp[i] = 0;
	else
	{
	dp[i] += dp[i + 1];
	int sum = (s[i] - '0') * 10 + (s[i + 1] - '0');
	if(sum <= 26)
	dp[i] += dp[i + 2];
	}
	}
	return dp[0];
	}
	};

view raw Decode Ways.cpp hosted with ❤ by GitHub