共计 1865 个字符，预计需要花费 5 分钟才能阅读完成。
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).
难度：medium
题目：一则数字消息由A到Z的字符编码，字符与数字的匹配关系如下
‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
给定非空字符串仅包含数字，判断它由多少种解码方式。
思路：动态规划，首先来分解一下问题状态转移方程
f(n) = f(n – 1) + f(n – 2) 当前字符在[1,9] 之间，且当前字符与前一字符组成的数在[11,19][21,26] 之间
f(n) = f(n – 1) 当前字符与前一字符组成的数不在[1,9][11,26] 之间
f(n) = f(n – 2) 当前字符与前一字符组成的数为 10 或 20
根据此方程可以使用递归实现，这是将想法实施的第一步。第二步优化，将递归实现转成迭代实现。
Runtime: 5470 ms, faster than 0.99% of Java online submissions for Decode Ways.Memory Usage: 50.2 MB, less than 0.97% of Java online submissions for Decode Ways.
class Solution {
public int numDecodings(String s) {
return numDecodings(s, s.length());
}
// length > 0
private int numDecodings(String s, int length) {
// 字符不为空 初始化 length0 为 1
if (0 == length) {
return 1;
}
if (1 == length) {
if (Integer.parseInt(s.substring(length – 1, length)) > 0) {
return 1;
}
return 0;
}
int last = length – 1;
int prev = last – 1;
int valLast = Integer.parseInt(s.substring(last, last + 1));
int valPrev = Integer.parseInt(s.substring(prev, prev + 2));
if (10 == valPrev || 20 == valPrev) {
return numDecodings(s, length – 2);
} else if (valPrev >= 10 && valPrev <= 26) {
return numDecodings(s, length – 1) + numDecodings(s, length – 2);
}
if (valLast > 0 && valLast < 10) {
return numDecodings(s, length – 1);
}
return 0;
}
}
Runtime: 3 ms, faster than 43.60% of Java online submissions for Decode Ways.Memory Usage: 34.6 MB, less than 3.09% of Java online submissions for Decode Ways.
class Solution {
public int numDecodings(String s) {
if (s.charAt(0) == ‘0’) {
return 0;
}
int p = 1, q = 1, result = 1;
for (int i = 1; i < s.length(); i++) {
int num1 = s.charAt(i) – ‘0’;
int num2 = Integer.valueOf(s.substring(i – 1, i + 1));
if (num2 == 10 || num2 == 20) {
result = p;
} else if (10 < num2 && num2 <= 26) {
result = p + q;
} else if (num1 > 0 && num1 < 10) {
result = q;
} else {
return 0;
}
p = q;
q = result;
}
return result;
}
}
