• Time:O(n)
• Space:O(n)

## C++

``````class Solution {
public:
int numDecodings(string s) {
const int n = s.length();
// dp[i] := # 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';
}
};
``````

## JAVA

``````class Solution {
public int numDecodings(String s) {
final int n = s.length();
// dp[i] := # 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';
}
}
``````

## Python

``````class Solution:
def numDecodings(self, s: str) -> int:
n = len(s)
# dp[i] := # of ways to decode s[i..n)
dp = [0] * n + [1]

def isValid(a: chr, 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]
``````