# [LeetCode] 91. Decode Ways 解码方法

2021年09月15日 阅读数：2

A message containing letters from `A-Z` is being encoded to numbers using the following mapping:html

```'A' -> 1
'B' -> 2
...
'Z' -> 26
```

Given a non-empty string containing only digits, determine the total number of ways to decode it.java

Example 1:python

```Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
```

Example 2:git

```Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).```

State: dp[i]，表明i以前的数字的解法数量。注意index：dp长度比数组多1，因此 s[i-1]是当前数字，dp[i]是当前数字的解法数。post

Function: dp[i] = dp[i - 1] (if s[i - 1] != 0) + dp[i - 2] (if s[i - 2] == 1 or s[i - 2] == 2 and i -1 < = 6)url

Initialize: dp[0] = 0, dp[1] = 1spa

Return: dp[n]code

Java: Recursive

``` int numDecodings(string s) {
return s.empty() ? 0: numDecodings(0,s);
}
int numDecodings(int p, string& s) {
int n = s.size();
if(p == n) return 1;
if(s[p] == '0') return 0;
int res = numDecodings(p+1,s);
if( p < n-1 && (s[p]=='1'|| (s[p]=='2'&& s[p+1]<'7'))) res += numDecodings(p+2,s);
return res;
}　　```

Java: Memoization O(n)

```int numDecodings(string s) {
int n = s.size();
vector<int> mem(n+1,-1);
mem[n]=1;
return s.empty()? 0 : num(0,s,mem);
}
int num(int i, string &s, vector<int> &mem) {
if(mem[i]>-1) return mem[i];
if(s[i]=='0') return mem[i] = 0;
int res = num(i+1,s,mem);
if(i<s.size()-1 && (s[i]=='1'||s[i]=='2'&&s[i+1]<'7')) res+=num(i+2,s,mem);
return mem[i] = res;
}　　```

Java: dp, O(n) time and space

```int numDecodings(string s) {
int n = s.size();
vector<int> dp(n+1);
dp[n] = 1;
for(int i=n-1;i>=0;i--) {
if(s[i]=='0') dp[i]=0;
else {
dp[i] = dp[i+1];
if(i<n-1 && (s[i]=='1'||s[i]=='2'&&s[i+1]<'7')) dp[i]+=dp[i+2];
}
}
return s.empty()? 0 : dp[0];
}
```

Java:　dp, constance space

```int numDecodings(string s) {
int p = 1, pp, n = s.size();
for(int i=n-1;i>=0;i--) {
int cur = s[i]=='0' ? 0 : p;
if(i<n-1 && (s[i]=='1'||s[i]=='2'&&s[i+1]<'7')) cur+=pp;
pp = p;
p = cur;
}
return s.empty()? 0 : p;
}　　```

Java:

```public class Solution {
public int numDecodings(String s) {
if (s.isEmpty() || (s.length() > 1 && s.charAt(0) == '0')) return 0;
int[] dp = new int[s.length() + 1];
dp[0] = 1;
for (int i = 1; i < dp.length; ++i) {
dp[i] = (s.charAt(i - 1) == '0') ? 0 : dp[i - 1];
if (i > 1 && (s.charAt(i - 2) == '1' || (s.charAt(i - 2) == '2' && s.charAt(i - 1) <= '6'))) {
dp[i] += dp[i - 2];
}
}
return dp[s.length()];
}
}
```

Java:

```public class Solution {
public int numDecodings(String s) {
if (s.isEmpty() || (s.length() > 1 && s.charAt(0) == '0')) return 0;
int prev = 1, prev_prev = 0;
for (int i = 0; i < s.length(); i++) {
int cur = 0;
if (s.charAt(i) != '0') {
cur = prev;
}
if (i > 0 && (s.charAt(i - 1) == '1' || (s.charAt(i - 1) == '2' && s.charAt(i - 1) <= '6'))) {
cur += prev_prev;
}
prev_prev = prev;
prev = cur;
}
return prev;
}
}
```

Python: wo

```class Solution(object):
def numDecodings(self, s):
"""
:type s: str
:rtype: int
"""
if len(s) == 0 or s[0] == '0':
return 0

dp = [0] * (len(s) + 1)
dp[0] = 1

for i in xrange(1, len(s) + 1):
if s[i-1] != '0':
dp[i] = dp[i-1]
if i > 1 and (s[i-2] == '1' or (s[i-2] == '2' and int(s[i-1]) <= 6)):
dp[i] += dp[i-2]

return dp[-1] 　　　　```

Python:

```class Solution(object):
def numDecodings(self, s):
if len(s) == 0 or s[0] == '0':
return 0
prev, prev_prev = 1, 0
for i in xrange(len(s)):
cur = 0
if s[i] != '0':
cur = prev
if i > 0 and (s[i - 1] == '1' or (s[i - 1] == '2' and s[i] <= '6')):
cur += prev_prev
prev, prev_prev = cur, prev
return prev
```

C++:

```class Solution {
public:
int numDecodings(string s) {
if (s.empty() || (s.size() > 1 && s[0] == '0')) return 0;
vector<int> dp(s.size() + 1, 0);
dp[0] = 1;
for (int i = 1; i < dp.size(); ++i) {
dp[i] = (s[i - 1] == '0') ? 0 : dp[i - 1];
if (i > 1 && (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6'))) {
dp[i] += dp[i - 2];
}
}
return dp.back();
}
};
```

C++:

```class Solution {
public:
int numDecodings(string s) {
if (s.empty()) return 0;
vector<int> dp(s.size() + 1, 0);
dp[0] = 1;
for (int i = 1; i < dp.size(); ++i) {
if (s[i - 1] != '0') dp[i] += dp[i - 1];
if (i >= 2 && s.substr(i - 2, 2) <= "26" && s.substr(i - 2, 2) >= "10") {
dp[i] += dp[i - 2];
}
}
return dp.back();
}
};
```

C++:

```class Solution {
public:
int numDecodings(string s) {
if (s.empty() || s.front() == '0') return 0;
int c1 = 1, c2 = 1;
for (int i = 1; i < s.size(); ++i) {
if (s[i] == '0') c1 = 0;
if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] <= '6')) {
c1 = c1 + c2;
c2 = c1 - c2;
} else {
c2 = c1;
}
}
return c1;
}
};
```

[LeetCode] 639. Decode Ways II 解码方法之二