题目：Decode Ways
将一串数字序列翻译成字母序列，找到可以翻译的种数。
‘A‘ -> 1 ‘B‘ -> 2 ... ‘Z‘ -> 26
思路：
数值小于2就有可能有不同的组合，其中1和2要分别处理
1的话一定可以有两种组合，2和要看后面一个数是否小于6.
class Solution { public: int numDecodings(string s) { int length = s.size(); if (length == 0) return 0; int *a = new int[length]; int pre = ‘0‘,cur; for (int i = 0; i < length; i++){ cur = s.at(i) - ‘0‘; int count = 0; int preC = pre - ‘0‘; int curC = ‘A‘ + 10 * preC + cur - 1; preC = ‘A‘ + preC - 1; if (curC >= ‘A‘ && curC <= ‘Z‘ && preC >= ‘A‘ && preC <= ‘Z‘){//加上前一个数 if (i > 1)count += a[i - 2]; else if (i == 1)count++; } curC = ‘A‘ + s.at(i) - ‘0‘ - 1; if (curC >= ‘A‘ && curC <= ‘Z‘){//不加前一个数 if (i > 0)count += a[i - 1]; else count++; } if (count == 0)return 0; a[i] = count; pre = s.at(i); } cur = a[length - 1]; delete a; return cur; } };
原文：http://www.cnblogs.com/yeqluofwupheng/p/6685648.html