【题目】
一条包含字母 A-Z
的消息通过以下方式进行了编码:
'A' ->
'B' ->
...
'Z' ->
给定一个只包含数字的非空字符串,请计算解码方法的总数。
示例 1:
输入: "12"
输出:
解释: 它可以解码为 "AB"( )或者 "L"()。
示例 2:
输入: "226"
输出:
解释: 它可以解码为 "BZ" ( ), "VF" ( ), 或者 "BBF" ( ) 。
【思路】
对于1,只有1种可能,对于11,有2种可能(1 1 和11),对于111,有3种可能(1 1 1、11 1、1 11),对于1111,有5种可能(1 1 1 1、11 1 1 、1 11 1、1 1 11、11 11),对于这样的组合,似乎有一个规律,f(n) = f(n-1) + f(n-2)(斐波那契数列)当然可以直观的理解:当第i个元素和第i-1个元素可以作为一种解码方式时,总的解码方式可以分为两组,一组是将第i个元素单独作为一种解码方式,另一组是将第i-1及第i个元素共同作为一种解码方式,各自有f(i-1)和f(i-2)种可能。
当第i个元素和第i-1个元素不可作为一种解码方式时,第i个元素为0,则解码方式总数为f(i-2);否则为f(i-1)。
还有一个特殊情况,第i个元素为0,第i-1个元素为0或者>2,不存在这种解码方式,返回0.
综上,将第i-1个元素和第i个元素转换为数字d,有以下递推公式:
f(n) = f(n-1) + f(n-2),当0 < d < 27
f(n-1),当d>=27,且d%10 != 0
f(n-2),当d==10,或d==20
0,其他情况
【代码】
python版本
class Solution(object):
def numDecodings(self, s):
"""
:type s: str
:rtype: int
"""
length = len(s)
i =
res = [] * length
if length == or s[] == '0':
return
if length == :
return
while i < length:
# s[i]为0的情况
if s[i] == '0':
res[i] = res[i-2] if i - >= else
if s[i-1] == '0' or s[i-1] > '2':
return
else:
res[i] = res[i-1]
# 1-26,特殊处理
if s[i-1] == '1' or (s[i-1] == '2' and '0' < s[i] < '7'):
res[i] += res[i-2] if i - >= else
# >27的情况,res[i] = res[i-1]
i +=
# print(res)
return res[-1]
C++版本
class Solution {
public:
int numDecodings(string s) {
if(s.size() == || s[] == '0')
return ;
vector<int> res(s.size(), );
for(int i=; i<s.size(); i++){
if(s[i] == '0'){
// 两个0,或者十位数大于2
if(s[i-1] == '0' || s[i-1] > '2')
return ;
// res[i] == res[i-2]
res[i] = ;
if(i-2 >= )
res[i] = res[i-2];
}else{
res[i] = res[i-1];
// 1-26,res[i] = res[i-1] + res[i-2]
if(s[i-1] == '1' || (s[i-1] == '2' && s[i] > '0' && s[i] < '7')){
if(i-2 < )
res[i] += ;
else
res[i] += res[i-2];
}
// >27,res[i] = res[i-1]
}
}
return res[res.size()-1];
}
};