# 91. Decode Ways

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

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

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

Example 1:

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

Example 2:

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

C++ 解法一：

``````class Solution {
public:
int numDecodings(string s) {
if (s.empty() || 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();
}
};
``````

Java 解法一：

``````class Solution {
public int numDecodings(String s) {
if (s.isEmpty() || 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()];
}
}
``````

C++ 解法二：

``````class Solution {
public:
int numDecodings(string s) {
if (s.empty() || s[0] == '0') 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();
}
};
``````

Java  解法二：

``````class Solution {
public int numDecodings(String s) {
if (s.isEmpty() || s.charAt(0) == '0') return 0;
int[] dp = new int[s.length() + 1];
dp[0] = 1;
for (int i = 1; i < dp.length; ++i) {
if (s.charAt(i - 1) != '0') dp[i] += dp[i - 1];
if (i >= 2 && (s.substring(i - 2, i).compareTo("10") >= 0 && s.substring(i - 2, i).compareTo("26") <= 0)) {
dp[i] += dp[i - 2];
}
}
return dp[s.length()];
}
}
``````

C++ 解法三：

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

Java 解法三：

``````class Solution {
public int numDecodings(String s) {
if (s.isEmpty() || s.charAt(0) == '0') return 0;
int a = 1, b = 1, n = s.length();
for (int i = 1; i < n; ++i) {
if (s.charAt(i) == '0') a = 0;
if (s.charAt(i - 1) == '1' || (s.charAt(i - 1) == '2' && s.charAt(i) <= '6')) {
a = a + b;
b = a - b;
} else {
b = a;
}
}
return a;
}
}
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/91

Decode Ways II

Climbing Stairs

https://leetcode.com/problems/decode-ways/discuss/30384/a-concise-dp-solution

https://leetcode.com/problems/decode-ways/discuss/30462/accepted-solution-to-decode-ways-no-need-to-take-care-of-0-case

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation