题意
有一个消息包含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; } }; |