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