Decode Ways
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.
算法思想：
直接dfs超时，需要加上纪录路径
class Solution {
public:
bool isValid(string s){
if(s[0]==‘0‘)return false;
int sum=0;
for(int i=0;i<s.size();i++){
sum*=10;
sum+=s[i]-‘0‘;
}
return sum>=1&&sum<=26;
}
int dfs(vector<int> &dp,string &s,int start){
if(start>=s.size())return 1;
if(dp[start]!=-1)return dp[start];
if(s[start]==‘0‘)return 0;
int sum=0;
for(int i=start;i<s.size()&&i-start<2;i++){
string sub=s.substr(start,i-start+1);
if(isValid(sub)){
sum+=dfs(dp,s,i+1);
}
}
dp[start]=sum;
return sum;
}
int numDecodings(string s) {
if(!s.size())return 0;
vector<int> dp;
dp.assign(s.size(),-1);
return dfs(dp,s,0);
}
};