一条包含字母 A-Z 的消息通过以下方式进行了编码：
‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。
示例 1:
输入: “12”
输出: 2
解释: 它可以解码为 “AB”（1 2）或者 “L”（12）。
示例 2:
输入: “226”
输出: 3
解释: 它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6)
题目链接：中文题目；英文题目
我们换一种思路来看待这道题：题目要求要么分解成单个字符，要么分解成两个字符，整个字符串分解完算一种拆解方法。那么这道题可以看成向前走一步或者走两步，如果能从序号0走到末尾序号，则算一种拆解方式。
说到这里，相似的题目我们见了不少呢：
所以我们可以用相似的思路来做这道题，但是有两个障碍条件：1）s[i] != ‘0’；2）9 < s[i, i + 1] < 27；前者表示单个字符不能为0，或两个字符首字符不能为0，比如"01"；后者表示两个字符代表的数字必须大于9，小于27；
接着使用Hash Table来查找两个字符所代表的数字是否合法，所以有如下步骤：
不用想这种方法肯定超时，这部分代码对应：2.2.1 暴力破解
但是有优化的余地：关于上面两个障碍条件，我们可以记录下来，如果下次遇到直接跳过，这样可以节约一定的时间。
1）s[i] != ‘0’：我们发现对于idx，只要后面有一个0，则不需要往后走了，所以先遍历string一遍，把为0的序号记录下来，走一步之前先二分查找是否后面有0，如果有则检查走两步；没有才继续往后走一步；
2）对于不满足s[i] == ‘0’；2）9 < s[i, i + 1] < 27，记录下idx，下次遇到直接跳过；
但是这种优化方法对于没有0的情况不是很理想，所以还是会超时。这部分代码对应：2.2.2 记忆（Memorization）
备注：upper_bound 和 lower_bound两个函数的使用方法可以参考这篇文章 - 34. 在排序数组中查找元素的第一个和最后一个位置
2.2.1 暴力破解
class Solution {
unordered_set<string> decode;
int count = 0;
void backtracking(string& s, int idx) {
if (idx == s.size()) { count++; return; }
if (s[idx] != '0') backtracking(s, idx + 1);
if (idx != static_cast<int>(s.size() - 1) && decode.count(s.substr(idx, 2))) backtracking(s, idx + 2);
}
public:
Solution() {
this->decode = {"10", "11", "12", "13", "14", "15", "16", "17", "18", "19", "20", "21", "22", "23", "24", "25", "26" }; // "0X"这种类型不算
}
int numDecodings(string s) {
backtracking(s, 0);
return this->count;
}
};
2.2.2 记忆（Memorization）
class Solution {
unordered_set<string> decode;
unordered_set<int> twoStepsProhibited;
vector<int> oneStepsProhibited;
int count = 0;
void backtracking(string& s, int idx) {
if (idx == s.size()) { count++; return; }
if (lower_bound(oneStepsProhibited.begin(), oneStepsProhibited.end(), idx) == oneStepsProhibited.end()) backtracking(s, idx + 1);
if (idx != static_cast<int>(s.size() - 1) && !twoStepsProhibited.count(idx) && decode.count(s.substr(idx, 2))) backtracking(s, idx + 2);
else twoStepsProhibited.insert(idx);
}
public:
Solution() {
this->decode = { "10", "11", "12", "13", "14", "15", "16", "17", "18", "19", "20", "21", "22", "23", "24", "25", "26" }; // "0X"这种类型不算
}
int numDecodings(string s) {
// s[i] == '0'的序号
for (int i = 0; i < s.size(); i++)
if (s[i] == '0') oneStepsProhibited.push_back(i);
backtracking(s, 0);
return this->count;
}
};
把这道题看成路径问题，那么动态规划是一个非常实用的方法，那来看看这道题如何利用DP来解题。根据上面的分析，某个位置所有的拆解总数等于后两个位置的总数：memo[i] = memo[i + 1] + memo[i + 2]。比如下面这个例子：
[1,2,3]
3有一种拆解方式，2有两种拆解方式：“2”, “3” 和 “23”，那么1的拆解方法总数等于2的总数 + 3的总数： 1 + 2 = 3；这是因为：如果1作为一个数字，那么拆解总数看2和3，也就是2的总数目；如果1和2作为一个数字，那么只有3一种可能，所以memo[i] = memo[i + 1] + memo[i + 2]；到这里我们明白了动态规划的公式，还差初始化条件，根据上面的分析，我们可以用len - 1 和 len - 2来作为起始状态，但是这样会有很多情况，比如"0"或"01"等不合法的情况，所以初始化len + 1个位置，memo[len] = 1，memo[len - 1]根据是否为0来判断是为1还是为0，从memo[len - 2]开始使用上面得到的公式进行计算即可；
同样，遇到0则不可能拆解，所以直接跳过；如果可能拆解成2位数，则memo[i] = memo[i + 1] + memo[i + 2]；反之，则memo[i] = memo[i +1]；至此动态规划的思路理解完毕，代码则有三种写法：
1）把上面的暴力破解的代码加入动态规划的思路，从后往前计算出一个idx的数目，存储起来，后面再次访问则可以直接返回对应数目；不过这个方法Java不超时，但是C++超时，对应Java代码见这里：[Java] Recursion, Top Down and Bottom Up。此部分对应代码：3.2.1 递归（Recursion, Time Limit Exceeded）
2）直接把上面的动态规划思路翻译成代码，用memo数组来储存之前的状态；此部分对应代码：3.2.2 迭代 + 额外空间（Iteration + Extra Space）
3）省略memo数组：因为公式memo[i] = memo[i + 1] + memo[i + 2] 或者 memo[i] = memo[i +1]，所以至多需要之前两个状态即可，再之前的都可以省去，根据这个思路，可以不使用额外空间；我们初始化first表示memo[i + 1]，second表示memo[i + 2]，digit表示当前的位数，preDigit表示上一轮的位数，整个思路流程示意如下图。此部分对应代码：3.2.3 迭代 + 无需额外空间（Iteration + Without Extra Space）
备注：关于stringstream的用法，可以参考这篇文章 - c++ 数字与字符串的相互转换
3.2.1 递归（Recursion, Time Limit Exceeded）
class Solution {
vector<int> memo;
int recursionMethodTopDown(string& s, int idx) {
if (memo[idx] > -1) memo[idx];
if (idx == s.size()) return 1;
int digit = s[idx] - '0';
int ans = digit > 0 ? recursionMethodTopDown(s, idx + 1) : 0; // memo[i] = s[i] == '0' ? memo[i + 1] : 0;
if (idx != static_cast<int>(s.size() - 1) && digit > 0)
ans += (digit * 10 + s[idx + 1] - '0') < 27 ? recursionMethodTopDown(s, idx + 2) : 0; // memo[i] += (s[i] != '0' && s[i, i + 1] < 27) ? memo[i + 2] : 0;
memo[idx] = ans;
return ans;
}
public:
int numDecodings(string s) {
this->memo = vector<int>(s.size() + 1, -1);
return recursionMethodTopDown(s, 0);
}
};
3.2.2 迭代 + 额外空间（Iteration + Extra Space）
class Solution {
// 将string转换为int
int convertToInt(string str) {
stringstream ss;
int num;
ss << str;
ss >> num;
return num;
}
public:
int numDecodings(string s) {
int len = s.size();
if (!len) return 0;
vector<int> memo(len + 1, 0);
memo[len] = 1;
memo[len - 1] = s[len - 1] == '0' ? 0 : 1;
for (int i = len - 2; i >= 0; i--) {
if (s[i] == '0') continue;
else memo[i] = convertToInt(s.substr(i, 2)) <= 26 ? memo[i + 1] + memo[i + 2] : memo[i + 1];
}
return memo[0];
}
};
3.2.3 迭代 + 无需额外空间（Iteration + Without Extra Space）
class Solution {
public:
int numDecodings(string s) {
int len = s.size(), second = 0, first = 1, ans = 0, digit = -1, preDigit = 27;
for (int i = len - 1; i >= 0; i--) {
digit = s[i] - '0';
ans = digit > 0 ? first : 0; // memo[i] = s[i] == '0' ? memo[i + 1] : 0;
ans += (digit > 0 && (digit * 10 + preDigit) < 27) ? second : 0; // memo[i] += (s[i] != '0' && s[i, i + 1] < 27) ? memo[i + 2] : 0;
second = first; first = ans; // 存储本轮的memo[i] 和 memo[i + 1]，即下一轮的memo[i + 1] 和 memo[i + 2];
preDigit = digit;
}
return ans;
}
};
这个星期开始研一就要开课啦，所以后面题目更新就比较佛系啦。如果大家想看某道题的解析，可以留言或者私信微信（fengkeyleaf）、QQ（402951678）都可以啦，我会把解法代码和详细思路尽量整理发出来哒，争取每个人都能看懂一道题究竟是怎么解决哒，杜绝似懂非懂的理解哒~
