题意
有一个消息包含A-Z通过以下规则编码：
|
1 2 3 4 5 |
'A' -> 1 'B' -> 2 ... 'Z' -> 26 |
现在给你一个加密过后的消息，问有几种解码的方式 ？如给出消息“12”，有两种解码的方法 AB(12) 或者 L(12)，所以返回 2。
思路
这道题其实和爬楼梯非常相似。我们知道爬楼梯的递推公式为：f(n) = f(n-1)+f(n-2)。这道题也有类似的公式，不过由于解码时输入需要在码表所规定的范围内，所以可能有f(n) = f(n-1)+f(n-2)，可能有f(n) = f(n-1)，还可能有f(n) = f(n-2)，分别对应下面三种情况：
- “XXX123″，这个字符串可以拆成”XXX1″和”23″，也可以拆成”XXX12″和”3″，因此
f(n) = f(n-1)+f(n-2) - “XXX120″，这个字符串只能拆成”XXX1″和”20″，因此
f(n) = f(n-2) - “XXX127″，这个字符串只能拆成”XXX12″和”7″，因此
f(n) = f(n-1)
实现
由上述条件及相应的递推公式，实现如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class Solution { public: int decodeWays(string s) { if (s.empty() || s[0] == '0') { return 0; } int cur = 1, prev = 0; for(size_t i = 1; i <= s.size(); i++) { if (s[i-1] == '0') { cur = 0; } if (i < 2 || !(s[i-1] == '1' || (s[i-2] == '2' && s[i-1] <= '6'))) { prev = 0; } int tmp = cur; cur = tmp + prev; prev = tmp; } return cur; } }; |