A message containing letters from
'A' -> 1A-Z is being encoded to numbers using the following mapping:'B' -> 2
...
'Z' -> 26
Given encoded message
"12", it could be decoded as "AB" (1 2) or "L" (12).
Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Solution:
int numDecodings(string s) {
if(s.size() == 0)
return 0;
vector<int> ways(s.size() + 1,0);
ways[s.size()] =1;
for(int i = s.size() - 1; i >= 0; --i)
{
//one digit number
if(s[i] == '0')
ways[i] = 0;
else
ways[i] = ways[i+1];
//two digit number
if( i + 1 < s.size() && ((s[i] == '1' || (s[i] == '2' && s[i + 1] <= '6')))) {
ways[i] += ways[i + 2];
}
}
return ways[0];
}
No comments:
Post a Comment