leetcode 解码方法数
题目描述:
一条包含字母 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) 。
这道题是一个动态规划的题,我们记录字符串为S,我们按照顺序对S的字串求值,最后就能得到最终值。时间复杂度O(n),空间负责度O(n)。
我们记f(n)表示从S的从0到n的子串的编码数目
分三种情况考虑:
1.当S[n] = '0',这种情况下,我们知道出现0的情况只可能是10或者20,单独的0是不存在的,因此这种情况下
f(n) = f(n-2);
2.S[n] != '0' && (S[n-1]S[n]组成的数字小于26且大于10)
f(n) = f(n-1) + f(n-2)
3.S[n] != '0' && (S[n-1]S[n]组成的数字大于26或者小于10)
f(n) = f(n-1)
代码如下:
class Solution {
public:
int numDecodings(string s)
{
if(s.size() == 0 || s[0] == '0')
{
return 0;
}
vector<int> subret(s.size(),0);
subret[0] = 1;
if(s.size() < 2)
{
return 1;
}
if(s[1] == '0')
{
if(s[0] != '1' && s[0] != '2')
{
return 0;
}
subret[1] = 1;
}
else
{
int num = stoi(s.substr(0,2));
if(num >26)
{
subret[1] = 1;
}
else
{
subret[1] = 2;
}
}
for(int i = 2; i < s.size(); i++)
{
if(s[i] == '0')
{
if(s[i - 1] != '1' && s[i - 1] != '2')
{
return 0;
}
subret[i] = subret[i - 2];
}
else
{
int num = stoi(s.substr(i-1,2));
if(num < 10 || num >26)
{
subret[i] = subret[i-1];
}
else
{
subret[i] = subret[i-1] + subret[i - 2];
}
}
}
return subret[s.size() -1];
}
};