Skip to content

91. Decode Ways

  • Time: $O(n)$
  • Space: $O(n)$
 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
class Solution {
 public:
  int numDecodings(string s) {
    const int n = s.length();
    // dp[i] := the number of ways to decode s[i..n)
    vector<int> dp(n + 1);
    dp[n] = 1;  // ""
    dp[n - 1] = isValid(s[n - 1]);

    for (int i = n - 2; i >= 0; --i) {
      if (isValid(s[i]))
        dp[i] += dp[i + 1];
      if (isValid(s[i], s[i + 1]))
        dp[i] += dp[i + 2];
    }

    return dp[0];
  }

 private:
  bool isValid(char c) {
    return c != '0';
  }

  bool isValid(char c1, char c2) {
    return c1 == '1' || c1 == '2' && c2 < '7';
  }
};

 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
class Solution {
  public int numDecodings(String s) {
    final int n = s.length();
    // dp[i] := the number of ways to decode s[i..n)
    int[] dp = new int[n + 1];
    dp[n] = 1; // ""
    dp[n - 1] = isValid(s.charAt(n - 1)) ? 1 : 0;

    for (int i = n - 2; i >= 0; --i) {
      if (isValid(s.charAt(i)))
        dp[i] += dp[i + 1];
      if (isValid(s.charAt(i), s.charAt(i + 1)))
        dp[i] += dp[i + 2];
    }

    return dp[0];
  }

  private boolean isValid(char c) {
    return c != '0';
  }

  private boolean isValid(char c1, char c2) {
    return c1 == '1' || c1 == '2' && c2 < '7';
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
  def numDecodings(self, s: str) -> int:
    n = len(s)
    # dp[i] := the number of ways to decode s[i..n)
    dp = [0] * n + [1]

    def isValid(a: str, b=None) -> bool:
      if b:
        return a == '1' or a == '2' and b < '7'
      return a != '0'

    if isValid(s[-1]):
      dp[n - 1] = 1

    for i in reversed(range(n - 1)):
      if isValid(s[i]):
        dp[i] += dp[i + 1]
      if isValid(s[i], s[i + 1]):
        dp[i] += dp[i + 2]

    return dp[0]