顿搜
飞过闲红千叶，夕岸在哪
类目归类
[LeetCode 91] Decode Ways [Java]
03/27
1. Description
A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
2. Example
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.
3. Explanation
Let dp[i] stands for the number of ways decoding s(0, i)
(1). dp[0] = 1
(2).
$$dp\lbrack1\rbrack={\{\begin{array}{ll}\hspace{1em}\text{if}\hspace{1em}s(0,1)>26\vert\vert s\lbrack1\rbrack\operatorname{==}0\\\hspace{1em}\text{if}\hspace{1em}s(0,1)\leq26\&\&s\lbrack1\rbrack!=0\end{array}}$$
(3).
$$dp\lbrack i\rbrack={\{\begin{array}{ll}dp\lbrack i-1\rbrack,\hspace{1em}\text{if}\hspace{1em}s(i-1,i)>26\vert\vert s\lbrack i\rbrack\operatorname{==}0\\dp\lbrack i-1\rbrack+dp\lbrack i-2\rbrack,\hspace{1em}\text{if}\hspace{1em}s(i-1,i)\leq26\&\&s\lbrack i\rbrack!=0\end{array}}$$
4. Code
public class LeetCode0091 {
public int numDecodings(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int[] dp = new int[s.length() + 1];
dp[0] = 1;
int pre = s.charAt(0) - '0';
if (pre == 0) {
return 0;
} else {
dp[1] = dp[0];
}
for (int i = 1; i < s.length(); i++) {
int current = s.charAt(i) - '0';
int num = pre * 10 + current;
if (num == 0 || current == 0 && pre > 2) {
return 0;
}
if (num == 10 || num == 20) {
dp[i + 1] = dp[i];
} else {
dp[i + 1] = dp[i];
if (num < 27 && num > 10) {
dp[i + 1] += dp[i - 1];
}
}
pre = current;
}
return dp[s.length()];
}
public static void main(String[] args) {
LeetCode0091 leetcode = new LeetCode0091();
System.out.println(leetcode.numDecodings("1212"));
}
}
