2026/04/04

[LeetCode] 91 Decode Ways 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
  int numDecodings(string s) {
    constexpr int SIZE = 101;
    int dp[SIZE];
    if (s[0] == '0')
      return 0;
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2, j = 1; i <= s.length(); i++, j++) {
      dp[i] = 0;
      if (s[j] != '0')
        dp[i] += dp[i - 1];
      if (s[j - 1] == '1' || (s[j  - 1] == '2' && s[j] <= '6'))
        dp[i] += dp[i - 2];      
    }
    return dp[s.length()];
  }
};
Labels: