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
Given encoded message
"12"
, it could be decoded as "AB"
(1 2) or "L"
(12).
The number of ways decoding
» Solve this problem"12"
is 2.
[Thoughts]
Similar as "[LeetCode] Climbing Stairs, Solution". DP. Just add some logic to compare character.
Transformation function as:
Count[i] = Count[i-1] if S[i-1] is a valid char
or = Count[i-1]+ Count[i-2] if S[i-1] and S[i-2] together is still a valid char.
[Code]
1: int numDecodings(string s) {
2: if(s.empty() || s[0] =='0') return 0;
3: if(s.size() ==1) return check(s[0]);
4: int fn=0, fn_1=0, fn_2=1;
5: fn_1 = (check(s[0]) * check(s[1]))+check(s[0], s[1]);
6: for(int i=2; i< s.size(); i++)
7: {
8: if(check(s[i])) fn+= fn_1;
9: if(check(s[i-1], s[i])) fn+=fn_2;
10: if(fn ==0)
11: return 0;
12: fn_2 = fn_1;
13: fn_1 = fn;
14: fn=0;
15: }
16: return fn_1;
17: }
18: int check(char one)
19: {
20: return (one != '0') ? 1 : 0;
21: }
22: int check(char one, char two)
23: {
24: return (one == '1' || (one == '2' && two <= '6'))
25: ? 1 : 0;
26: }
No comments:
Post a Comment