A message containing letters from A-Z
is being encoded to numbers using the following mapping:
'A' -> 1 'B' -> 2 ... 'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message "12"
, it could be decoded as "AB"
(1 2) or "L"
(12).
The number of ways decoding "12"
is 2.
参考:http://www.cnblogs.com/TenosDoIt/p/3451920.html
分析:需要注意的是,如果序列中有不能匹配的0,那么解码方法是0,比如序列012 、100(第二个0可以和1组成10,第三个0不能匹配)。递归的解法很容易,但是大集合会超时。转换成动态规划的方法,假设dp[i]表示序列s[0...i-1]的解码数目,动态规划方程如下:
- 初始条件:dp[0] = 1, dp[1] = (s[0] == '0') ? 0 : 1
- dp[i] = ( s[i-1] == 0 ? 0 : dp[i-1] ) + ( s[i-2,i-1]可以表示字母 ? dp[i-2] : 0 ), 其中第一个分量是把s[0...i-1]末尾一个数字当做一个字母来考虑,第二个分量是把s[0...i-1]末尾两个数字当做一个字母来考虑
C++实现代码:(为什么dp要有n+1的长度呢,除了s[0]以外,每次s[i]与两个元素有关,所以使用dp[0]记为1,s[0]的记录存放在dp[1]中。
#include<iostream> #include<string> using namespace std; class Solution { public: int numDecodings(string s) { if(s.empty()) return 0; int n=s.size(); int dp[n+1]; //dp[i]表示s[0...i-1]的解码方法数目 dp[0]=1; if(s[0]=='0') dp[1]=0; else dp[1]=1; int i; for(i=2;i<n+1;i++) { if(s[i-1]=='0') dp[i]=0; else dp[i]=dp[i-1]; if((s[i-2]=='2'&&s[i-1]<='6')||(s[i-2]=='1')) dp[i]+=dp[i-2]; } return dp[n]; } }; int main() { Solution s; cout<<s.numDecodings(string("123456"))<<endl; }
时间: 2024-10-23 21:46:50