Sunday, January 27, 2013

[LeetCode] Decode Ways, Solution

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.
» Solve this problem

[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') return 0;
3:      if(s.size() ==1) return check(s);
4:      int fn=0, fn_1=0, fn_2=1;
5:      fn_1 = (check(s) * check(s))+check(s, s);
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:    }
``````