LeetCode_091: DecodeWays 从DFS到动态规划

从LeetCode中有一些数字字符串处理问题，它们的解法有许多相似之处，但是在具体操作上又有所不同，91题和93题IPAddress就是比较好的范例。这篇博客主要从DFS和DP两种方法来分析问题，并判断适应问题环境使用合适的方法。

题目

A message containing letters from A-Z is being encoded to numbers using the following mapping:

‘A’ -> 1 ‘B’ -> 2 … ‘Z’ -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

DFS

首先，应该注意到这类数字字符串题目，要特别注意 “0” 这个字符的处理，这个在91题和93题中都有反映。

博主首先想到的是DFS的方法，具体操作起来就是按照一定规则不断枚举，然后统计解码方法的数量。如果选用DFS算法，那么应该意识到，这是在枚举解，如果没有很好的剪枝策略，算法开销将非常巨大。在题目要求枚举出解的时候，我们应该考虑DFS算法（比如 93题）。而在这一题中，DFS算法是不合适的，我们最后需要的只是一个数量 ，于是我们选择动态规划。（其实博主第一次DFS超时了0.0）

DP

每增加一个字符，根据情况会导致数量的变化，这里注意增加0，可能导致失败，也可能导致前面的字符必须和0匹配导致回退。我们这里要考虑两种 “0” 存在的情况，具体的直接看代码吧。

代码

还是特别强调对字符”0″ 的处理：

class Solution {
public:
	int numDecodings(string s){
		const int n = s.size();
		if (n == 0 || s[0] == '0'){
			return 0;
		} else if(n == 1){
			return 1;
		}
		int pprev = 1;
		int prev = 1;
		int cur = 1;
		for (int i = 1; i < n; ++i){
			int num = atoi(s.substr(i - 1, 2).c_str());
			if (s[i] == '0' && (s[i - 1] == '0' || num > 26)){
				return 0;
			}
			if (num <= 26){
				if (s[i] == '0'){
					cur = pprev;
					prev = cur;
				} else if (s[i-1] != '0'){
					cur += pprev;
				}
			}
			pprev = prev;
			prev = cur;
		}
		return cur;
	}
};