【leetcode刷题】T69-解码方法
【题目】
一条包含字母 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];
}
};本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-05-23，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读