## 题目地址

https://leetcode.com/problems/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;
}
}

### 思路2

• 对于一个数字来说[1,9]这九个数字能够被识别为一种编码方式
• 对于两个数字来说[10, 26]这几个数字能被识别为一种编码方式

dp[i] = 以自身去编码（一位） + 以前面的元素和自身去编码（两位） .这显然是完备的，

## 关键点解析

• 爬楼梯问题（我把这种题目统称为爬楼梯问题）

## 代码

/*
* @lc app=leetcode id=91 lang=javascript
*
* [91] Decode Ways
*
* https://leetcode.com/problems/decode-ways/description/
*
* algorithms
* Medium (21.93%)
* Total Accepted:    254.4K
* Total Submissions: 1.1M
* Testcase Example:  '"12"'
*
* 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).
*
*/
/**
* @param {string} s
* @return {number}
*/
var numDecodings = function(s) {
if (s == null || s.length == 0) {
return 0;
}
const dp = Array(s.length + 1).fill(0);
dp[0] = 1;
dp[1] = s[0] !== "0" ? 1 : 0;
for (let i = 2; i < s.length + 1; i++) {
const one = +s.slice(i - 1, i);
const two = +s.slice(i - 2, i);

if (two >= 10 && two <= 26) {
dp[i] = dp[i - 2];
}

if (one >= 1 && one <= 9) {
dp[i] += dp[i - 1];
}
}

return dp[dp.length - 1];
};

评论
0 评论