- Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.
- This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.
Leetcode -639- Decoding method II
[Blog link]
The path to learning at 🐔
The nuggets home page
[答 案]
Topic link
[making address]
Making the address
[B].
A message containing the letters A-Z is encoded as follows:
‘A’ -> 1 ‘B’ -> 2 … ‘Z’ -> 26 To decode an encoded message, all numbers must be grouped and then reversely mapped back to letters in the original encoding scheme (there may be many ways). For example, “11106” can be mapped to:
“AAJF” corresponds to groups (11 10 6) “KJF” corresponds to groups (11 10 6) Note that groups like (1 11 06) are not valid because “06” cannot be mapped to ‘F’ because “6” is different from “06”.
In addition to the alphanumeric mapping scheme described above, encoded messages may contain ‘*’ characters that can represent any number from ‘1’ to ‘9’ (excluding ‘0’). For example, the encoding string “1*” can represent any message of “11”, “12”, “13”, “14”, “15”, “16”, “17”, “18”, or “19”. Decoding “1*” is equivalent to decoding any encoded message that the string can represent.
You are given a string s, which consists of numbers and ‘*’ characters and returns the number of methods to decode the string.
Because the number of answers can be very large, return mod 109 + 7.
Example 1:
Input: s = "*" Output: 9 Explanation: This encoded message can represent any of "1", "2", "3", "4", "5", "6", "7", "8", or "9". Can be decoded into string "A", "B", "C", "D", "E", "F", "G", "H" and "I". Therefore, there are 9 decoding methods for "*".Copy the codeExample 2:
Input: s = "1*" Output: 18 Description: This encoded message can represent any of "11", "12", "13", "14", "15", "16", "17", "18", or "19". Each message can be decoded in two ways (for example, "11" can be decoded to "AA" or "K"). Therefore, "1*" has a total of 9 * 2 = 18 decoding methods.Copy the codeExample 3:
Input: s = "2*" Output: 15 Description: This encoded message can represent any of "21", "22", "23", "24", "25", "26", "27", "28", or "29". "21", "22", "23", "24", "25" and "26" have two decoding methods, but "27", "28" and "29" have only one decoding method. Therefore, "2*" has a total of (6 * 2) + (3 * 1) = 12 + 3 = 15 decoding methods.Copy the codeTip:
- 1 <= s.length <= 105
- S [I] is a digit or character ‘*’ in 0-9.
Idea 1: Dynamic planning
- The idea of DP is quite clear
- The difficulty is to organize a group discussion plan without leakage or repetition
- Define a dp[] array: dp[I] represents the number of schemes ending in the i-th character
- Let’s start the group discussion:
- In this case, it is not clear that use cases can be decoded, so a certain corner case is needed
- Returns 0 directly when there are consecutive zeros or a starting 0
- And then there’s a very complicated classification discussion
- The current positionCur for *
- Need to judge the pre position why
- If pre is * :
- i >= 2 :dp[i] = dp[i – 2] * 15; (Corresponding to the 15 numbers 11-19,21-26)
- dp[i] = 15;
- pre = ‘1’
- i >= 2 :dp[i] = dp[i – 2] * 9;
- dp[i] = 9;
- pre = ‘2’
- i >= 2 :dp[i] = dp[i – 2] * 6;
- dp[i] = 6;
- If pre is * :
- Dp [I]+=dp[I -1]*9
- Need to judge the pre position why
- The current positionCur 0
- Meets the decoding requirements
- pre = ‘*’ : i >=2? dp[i]= dp[i-2]*2:2;
- dp[i] = i>=2? dp[i-2]:1;
- Meets the decoding requirements
- The current positionCur for other characters
- pre = 0: dp[i] = dp[i – 1];
- pre = 1: i >=2? dp[i] = dp[i – 1] + dp[i – 2]; :dp[i-1]+1
- pre = 2:
- cur <= 6: i >=2? dp[i] = dp[i – 1] + dp[i – 2]*2; :dp[i-1]+1
- cur > 6: dp[i] = dp[i – 1];
- pre = *:
- cur <= 6: i >=2? dp[i] = dp[i – 1] + dp[i – 2]; :dp[i-1]+1
- cur > 6: dp[i] = dp[i – 1];
- Dp [I] = dp[i-1];
- Finally, because the value is very large, you need to do mod processing
- My judgment logic is a little complicated, can do a space to reduce the boundary judgment
public int numDecodings(String s) {
if (s.startsWith("0") || s.contains("00")) {
return 0;
}
int MOD = (int) 1e9 + 7;
long[] dp = new long[s.length()];
dp[0] = s.charAt(0) = =The '*' ? 9 : 1;
for (int i = 1; i < s.length(); i++) {
char cur = s.charAt(i), pre = s.charAt(i - 1);
if (cur == The '*') {
if (pre == The '*') {
if (i >= 2) {
dp[i] = dp[i - 2] * 15;
} else {
dp[i] = 15; }}if (pre == '1') {
if (i >= 2) {
dp[i] = dp[i - 2] * 9;
} else {
dp[i] = 9; }}if (pre == '2') {
if (i >= 2) {
dp[i] = dp[i - 2] * 6;
} else {
dp[i] = 6;
}
}
dp[i] += dp[i - 1] * 9;
} else if (cur == '0') {
if (pre == The '*') {
if (i >= 2) {
dp[i] = dp[i - 2] * 2;
} else {
dp[i] = 2; }}else if (pre <= '2') {
if (i >= 2) {
dp[i] = dp[i - 2];
} else {
dp[i] = 1; }}else {
return 0; }}else {
if (pre == '0') {
dp[i] = dp[i - 1];
} else if (pre == '1') {
if (i >= 2) {
dp[i] = dp[i - 1] + dp[i - 2];
} else {
dp[i] = dp[i - 1] + 1; }}else if (pre == '2') {
if (cur <= '6') {
if (i >= 2) {
dp[i] = dp[i - 1] + dp[i - 2];
} else {
dp[i] = dp[i - 1] + 1; }}else {
dp[i] = dp[i - 1]; }}else if (pre == The '*') {
if (cur <= '6') {
if (i >= 2) {
dp[i] = dp[i - 1] + dp[i - 2] * 2;
} else {
dp[i] = dp[i - 1] + 2; }}else {
if (i >= 2) {
dp[i] = dp[i - 1] + dp[i - 2];
} else {
dp[i] = dp[i - 1] + 1; }}}else {
dp[i] = dp[i - 1];
}
}
dp[i]%=MOD;
}
return (int) dp[s.length() - 1];
}
Copy the code- Time complexity O(n)
- Space complexity O(n)
Idea 2: scrolling array + dynamic programming
- According to the transfer equation, it is easy to find optimization using a scrolling array
- Use three Leaf’s code!
class Solution {
int mod = (int)1e9+7;
public int numDecodings(String s) {
int n = s.length() + 1;
long[] f = new long[3];
f[0] = 1;
f[1] = s.charAt(0) = =The '*' ? 9 : (s.charAt(0) != '0' ? 1 : 0);
for (int i = 2; i < n; i++) {
char c = s.charAt(i - 1), prev = s.charAt(i - 2);
int p1 = (i - 1) % 3, p2 = (i - 2) % 3;
long cnt = 0;
if (c == The '*') {
// cs[I] is a separate item
cnt += f[p1] * 9;
// cs[I] is used as an item together with the preceding character
if (prev == The '*') {
cnt += f[p2] * 15;
} else {
int u = (int)(prev - '0');
if (u == 1) cnt += f[p2] * 9;
else if (u == 2) cnt += f[p2] * 6; }}else {
int t = (int)(c - '0');
if (prev == The '*') {
if (t == 0) {
cnt += f[p2]* 2;
} else {
// cs[I] is a separate item
cnt += f[p1];
// cs[I] is used as an item together with the preceding character
if (t <= 6) cnt += f[p2] * 2;
elsecnt += f[p2]; }}else {
int u = (int)(prev - '0');
if (t == 0) {
if (u == 1 || u == 2) cnt += f[p2];
} else {
// cs[I] is a separate item
cnt += f[p1];
// cs[I] is used as an item together with the preceding character
if (u == 1) cnt += f[p2];
else if (u == 2 && t <= 6) cnt += f[p2];
}
}
}
f[i % 3] = cnt % mod;
}
return (int)(f[(n - 1) % 3]); }}Copy the code- Time complexity O(n)
- Space complexity O(1)