# 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 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]