91. 解码方法

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

考点

  • 划分DP
  • 滚动数组

思路

划分DP裸题，不再赘述

需要注意，由于最多只有两位数，所以只需要用两个变量即可替代数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
 public:
  int numDecodings(string s) {
    int n = s.size();
    s = "0" + s;
    int b = 1, a = s[1] == '0' ? 0 : 1;
    for (int i = 2; i <= n; ++i) {
      int res = 0;
      if (s[i] != '0') res += a;
      int t = (s[i - 1] - '0') * 10 + s[i] - '0';
      if (s[i - 1] != '0' && t >= 1 && t <= 26) res += b;
      b = a, a = res;
    }
    return a;
  }
};