Difficulty:: Medium
A message containing letters from A-Z is being encoded to numbers using the following mapping:
1
2
3
4
| '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:
1
2
3
| Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
|
Example 2:
1
2
3
| Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
|
Solution
Language: Java
从后往前
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public int numDecodings(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int n = s.length();
int[] dp = new int[n + 2];
dp[n] = 1;
for (int i = n - 1; i >= 0; i--) {
if (s.charAt(i) != '0') {
dp[i] = dp[i + 1];
}
if (i < n - 1) {
int d = (s.charAt(i) - '0') * 10 + s.charAt(i + 1) - '0';
if (d >= 10 && d <= 26) {
dp[i] += dp[i + 2];
}
}
}
return dp[0];
}
}
|
从前往后
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public int numDecodings(String s) {
if (s == null || s.length() == 0 || s.equals("0")) {
return 0;
}
int[] count = new int[s.length() + 1];
count[0] = 1;
for (int i = 0; i < s.length(); i++) {
if (i == 0) {
if (s.charAt(i) == '0') {
return 0;
} else {
count[i + 1] = 1;
}
} else if (s.charAt(i) == '0') {
if (s.charAt(i - 1) != '1' && s.charAt(i - 1) != '2') {
return 0;
}
count[i + 1] = count[i - 1];
} else if (s.charAt(i - 1) == '1' || (s.charAt(i - 1) == '2' && s.charAt(i) >= '0' && s.charAt(i) <= '6')) {
count[i + 1] = count[i] + count[i - 1];
} else {
count[i + 1] = count[i];
}
}
return count[s.length()];
}
}
|