639. 解码方法 II

发表于 分类于 阅读次数： Waline： 本文字数： 201 阅读时长 ≈ 1 分钟

考点

  • 划分DP
  • 滚动数组

思路

同这道题，只是多了一点判断，不再赘述

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
class Solution {
 public:
  static const int mod = 1e9 + 7;
  void add(long long& x, long long y) {
    x = (x + y) % mod;
    return;
  }
  int numDecodings(string s) {
    int n = s.size();
    s = "0" + s;
    long long b = 1, a = s[1] == '0' ? 0 : (s[1] == '*' ? 9 : 1);
    for (int i = 2; i <= n; ++i) {
      long long res = 0;
      // 区间只有一位
      if (s[i] != '0') add(res, isdigit(s[i]) ? a : 9 * a);
      // 区间有两位
      if (s[i - 1] != '0') {
        if (s[i] == '*' && s[i - 1] == '*')
          add(res, 15 * b);
        else if (s[i] == '*') {
          int x = s[i - 1] - '0';
          if (x == 1)
            add(res, b * 9);
          else if (x == 2)
            add(res, b * 6);
        } else if (s[i - 1] == '*') {
          int x = s[i] - '0';
          if (x >= 0 && x <= 6)
            add(res, b * 2);
          else if (x >= 7 && x <= 9)
            add(res, b);
        } else {
          int x = s[i] - '0' + (s[i - 1] - '0') * 10;
          if (x >= 1 && x <= 26) add(res, b);
        }
      }
      b = a, a = res;
    }
    return a;
  }
};