终于写完项目了，今天开始恢复每日LeetCode的练习。关于项目的总结，这两天尽量写一篇总结的博客，遇到的问题还是挺多的，尤其是在发布的时候，各种莫名其妙的bug。感谢室友的帮助，最后总算是赶出来了。
下面还是看看新的LeetCode题目，不知道是不是好久不写了，今天这两题都没做出来￣□￣｜｜，好好整理一下。
Decode Ways
原题链接
这题上来我的思路就是递归，先递归再说，最后面临长字符串的输入出现了时间超限。
看到discuss里的动态规划的思路，感到豁然开朗。
我们假设一个输入的字符串，.......123......，我们挑中间一段数，不管前后
r2意思是解码到这个位置的可能性的个数，r1的位置意思解码到1这个位置可能性的个数
因为2这个位置这里可以解码为... +"12"+... 也可以解码为 ...+"1"+"2"+...所以一共有r1+r2种
动态规划的更新就很明显了。
class Solution {
public:int numDecodings(string s) {if (s.empty() || s[0] == '0') return 0;int *record = new int[s.size()+1];memset(record, 0, sizeof(int)*(1+s.size()));record[0] = 1; record[1] = 1;for (int i = 1; i < s.size(); i++){if (s[i] == '0'){record[i] = 0;}if (s[i - 1] == '1' ||( s[i - 1] == '2' && s[i] <= '6')){record[i+1] = record[i - 1] + record[i];}else{record[i + 1] = record[i];}}return record[s.size()];}
};代码中有一个record数组，record[i+1]记录解码到第i位置的方法数。
我们也会发现其实用到这个数组的地方只有数组的开始两位，因此可以简化至如下：（代码来自Discuss）
class Solution {
public:int numDecodings(string s) {if (!s.size() || s.front() == '0') return 0;// r2: decode ways of s[i-2] , r1: decode ways of s[i-1] int r1 = 1, r2 = 1;for (int i = 1; i < s.size(); i++) {// zero voids ways of the last because zero cannot be used separatelyif (s[i] == '0') r1 = 0;// possible two-digit letter, so new r1 is sum of both while new r2 is the old r1if (s[i - 1] == '1' || s[i - 1] == '2' && s[i] <= '6') {r1 = r2 + r1;r2 = r1 - r2;}// one-digit letter, no new way addedelse {r2 = r1;}}return r1;}
};++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Decode Ways II
原题链接
比起上一题，多了正则的部分，其实也就是多了几种情况，只是情况比较复杂也容易出现疏漏。举两个例子：
首先看这种情况，这种情况可以是从r1那直接接过来，也可以是从r2那接过来，*的表示范围是从1-9
所以 ？= r1 + 2*r2
这种情况下，？=r1+ 9*r2
（代码from discuss）
class Solution {
public:int numDecodings(string s) {int n = s.size(), p = 1000000007;// f2 is the answer to sub string ending at position i; Initially i = 0.long f1 = 1, f2 = helper(s.substr(0,1));// DP to get f2 for sub string ending at position n-1;for (int i = 1; i < n; i++) {long f3 = (f2*helper(s.substr(i, 1)))+(f1*helper(s.substr(i-1, 2)));f1 = f2;f2 = f3%p;}return f2;}
private:int helper(string s) {if (s.size() == 1) {if (s[0] == '*') return 9;return s[0] == '0'? 0:1;}// 11-26, except 20 because '*' is 1-9if (s == "**") return 15;else if (s[1] =='*') {if (s[0] =='1') return 9;return s[0] == '2'? 6:0;}else if (s[0] == '*') return s[1] <= '6'? 2:1;else // if two digits, it has to be in [10 26]; no leading 0return stoi(s) >= 10 && stoi(s) <= 26? 1:0; }
};