1. 题目概述
题目如下:
A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.
Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
题目的中文意思是给出一个字母和数字的映射,然后给出一串数字,返回对应的合法字母序列的个数.
2. 解题思路
首先用一个例子来分析一下.假设输入的数字是222,那么对应的输出结果是3.从左到右,只有2的时候对应的结果是1,22的时候对应的结果是2,分别为
2 2-> B B
22 -> V
222对应的结果是3,分别为
2 2 2-> B B B
22 2 -> V B
2 22 -> B V
在过程中我们可以发现
f(222) = f(22) + f(2)
所以很自然的想到动态规划.对于第i个数字子串对应的合法字母串数目,等于第i-1个子串和i-2个子串之和,如下所示
f[i] = f[i-1] + f[i-2]
接下来考虑特殊情况,假设输出的串为0,那么对应的输出应该为0,因为这个串无法映射到任意合法的字母串.所以我们知道,当起始字符串字母为0时,
f[1] = 0 if(s[0] == '0')
同理,接着考虑字符串28,这数字对应的合法字符串为1,如下所示
2 8 -> B F
28 -> None
28大于26,不对应任何字母.综上,我们可以得出完整的动态规划方程式
f[0] = 1
f[1] = (s[0] == '0')?0:1;
f[i] = (s[i]=='0')?0:f[i]+f[i-1]; //如果当前字母不为0,f[i]+=f[i-1]
f[i] = (s[i-1:s[i]] is valid) ?f[i]=f[i]+f[i-2]:0;//如果s[i-1:i]可以对应合法的字符串,f[i] = f[i] + f[i-2]
3. 题目代码
该题目的代码如下所示
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
int numDecodings(string s) {
if(s.size() == 0)return 0;
if(s.size() == 1){
if(s[0] == '0')return 0;
else{
return 1;
}
}
vector<int> gV(s.size()+1,0);
gV[0] = 1;
if(s[0] == '0'){
gV[1] = 0;
}
else{
gV[1] = 1;
}
//for(int i=0;i<gV.size();i++)cout<<i<<" "<<gV[i]<<endl;
for(int i=1;i<s.size();i++){
if(s[i] != '0'){
gV[i+1] += gV[i];
}
string sTemp = s.substr(i-1, 2);
//cout<<sTemp<<endl;
if(sTemp[0] != '0' && stoi(sTemp) > 0 && stoi(sTemp) <= 26){
gV[i+1] += gV[i-1];
}
}
return gV[s.size()];
}
};
int main() {
Solution se;
cout<<se.numDecodings("")<<endl;
cout<<se.numDecodings("01")<<endl;
cout<<se.numDecodings("1")<<endl;
cout<<se.numDecodings("11")<<endl;
cout<<se.numDecodings("100")<<endl;
cout<<se.numDecodings("226")<<endl;
return 0;
}