LeetCodeInCpp/decode_ways.cpp at master · yingl/LeetCodeInCpp · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
  int calc_decode_ways(string &s,
      int index,
      vector<int> &cached_ways) {
    int len = s.length();

    if (index >= len) {
      return 1;
    }
    else if (cached_ways[index] >= 0) {
      return cached_ways[index];
    }
    else {
      int v1 = s[index] - '0';
      int v2 = -1;

      if (0 == v1) {
        cached_ways[index] = 0;
        return 0;
      }
      else {
        int ways = calc_decode_ways(s, index + 1, cached_ways);

        if ((index + 1) < len) {
          v2 = v1 * 10 + (s[index + 1] - '0');

          if ((v1 >= 1) && (v2 <= 26)) {
            ways += calc_decode_ways(s, index + 2, cached_ways);
          }
        }

        cached_ways[index] = ways;

        return ways;
      }
    }
  }

  int numDecodings(string s) {
    int len = s.length();

    if (0 == len) {
      return 0;
    }

    vector<int> cached_ways(len, -1);

    calc_decode_ways(s, 0, cached_ways);

    return cached_ways[0];
  }
};