You are given a string s containing digits and the character '*'. The '*' character can represent any digit from '1' to '9'. Each digit or pair of digits can be mapped to a letter using the mapping: 'A' -> 1, 'B' -> 2, ..., 'Z' -> 26.
Your task is to determine how many different ways you can decode the string s, considering all possible interpretations of the '*' characters. The answer may be very large, so return it modulo 10^9 + 7.
s must be decoded as part of a valid mapping.'*' can take any value from '1' to '9' for each occurrence.1 to 26.s, modulo 10^9 + 7.
The problem is an extension of the classic "Decode Ways" problem, but now with the addition of the '*' wildcard. At first glance, one might consider generating all possible replacements for '*' and then counting the number of valid decodings for each. However, this brute-force approach quickly becomes infeasible as the number of '*' increases, since each one multiplies the number of possibilities by up to 9.
Instead, we recognize that this problem has overlapping subproblems and optimal substructure—key signs for applying dynamic programming (DP). We can build up the solution by considering, for each position in the string, how many ways the substring up to that point can be decoded, using previous results to efficiently compute the current answer.
The main challenge is carefully handling all the cases introduced by the '*' character, both when it appears alone and when it forms a two-digit number with the previous character.
We use dynamic programming to solve this problem efficiently. Let's break down the approach step by step:
dp[i] represent the number of ways to decode the substring s[0:i] (the first i characters).
dp[0] = 1 (empty string has one way to decode: do nothing)dp[1]: depends on s[0]. If s[0] == '*', there are 9 ways (for '1' to '9'); if s[0] == '0', zero ways; otherwise, one way.i from 2 to len(s):
s[i-1] == '*', it can be any digit from 1 to 9: add 9 * dp[i-1].s[i-1] != '0', add dp[i-1].s[i-2] and s[i-1] are digits, check if the two-digit number is between 10 and 26. If so, add dp[i-2].'*', enumerate all valid combinations and count how many are valid two-digit numbers from 10 to 26, multiplying by dp[i-2] accordingly.dp[i] % (10^9 + 7) at every step.
By carefully considering all cases for '*' and using DP, we efficiently count all valid decodings.
Let's walk through an example input: s = "1*"
dp[0] = 1 (for the empty string)
dp[1] = 1 (since s[0] = '1')
'*' can be any of '1' to '9', so 9 * dp[1] = 9 * 1 = 9
s[0] = '1', s[1] = '*'. Together, '1*' can be '11' to '19' (all valid), so 9 options: 9 * dp[0] = 9 * 1 = 9
dp[2] = 9 (single) + 9 (double) = 18
So, there are 18 ways to decode "1*".
'*' there are up to 9 possibilities, so time complexity is O(9^k * n), where k is the number of '*' characters and n is the string length. This is infeasible for large inputs.
By recognizing the structure of the problem and leveraging dynamic programming, we efficiently compute the number of ways to decode a string with digits and wildcards. The key is to account for all possibilities introduced by the '*' character, both as a single digit and as part of two-digit numbers. By carefully handling these cases and using only constant space, we achieve an elegant and optimal solution.
class Solution:
def numDecodings(self, s: str) -> int:
MOD = 10 ** 9 + 7
n = len(s)
if not s:
return 0
prev = 1 # dp[0]
curr = 9 if s[0] == '*' else (0 if s[0] == '0' else 1)
for i in range(1, n):
temp = 0
# Single digit
if s[i] == '*':
temp += 9 * curr
elif s[i] != '0':
temp += curr
# Two digits
if s[i-1] == '*' and s[i] == '*':
# '**' can be 11-19 and 21-26
temp += 15 * prev # 9 + 6
elif s[i-1] == '*':
if '0' <= s[i] <= '6':
temp += 2 * prev # '1x' and '2x'
elif '7' <= s[i] <= '9':
temp += prev # only '1x'
elif s[i] == '*':
if s[i-1] == '1':
temp += 9 * prev # '11'-'19'
elif s[i-1] == '2':
temp += 6 * prev # '21'-'26'
else:
two = int(s[i-1:i+1])
if 10 <= two <= 26:
temp += prev
temp %= MOD
prev, curr = curr, temp
return curr
class Solution {
public:
int numDecodings(string s) {
const int MOD = 1e9 + 7;
int n = s.size();
long prev = 1;
long curr = (s[0] == '*') ? 9 : (s[0] == '0' ? 0 : 1);
for (int i = 1; i < n; ++i) {
long temp = 0;
// Single digit
if (s[i] == '*') {
temp += 9 * curr;
} else if (s[i] != '0') {
temp += curr;
}
// Two digits
if (s[i-1] == '*' && s[i] == '*') {
temp += 15 * prev; // 11-19 and 21-26
} else if (s[i-1] == '*') {
if (s[i] >= '0' && s[i] <= '6') {
temp += 2 * prev;
} else if (s[i] >= '7' && s[i] <= '9') {
temp += prev;
}
} else if (s[i] == '*') {
if (s[i-1] == '1') {
temp += 9 * prev;
} else if (s[i-1] == '2') {
temp += 6 * prev;
}
} else {
int two = (s[i-1] - '0') * 10 + (s[i] - '0');
if (two >= 10 && two <= 26) {
temp += prev;
}
}
temp %= MOD;
prev = curr;
curr = temp;
}
return (int)curr;
}
};
class Solution {
public int numDecodings(String s) {
int MOD = 1000000007;
int n = s.length();
long prev = 1;
long curr = (s.charAt(0) == '*') ? 9 : (s.charAt(0) == '0' ? 0 : 1);
for (int i = 1; i < n; ++i) {
long temp = 0;
// Single digit
if (s.charAt(i) == '*') {
temp += 9 * curr;
} else if (s.charAt(i) != '0') {
temp += curr;
}
// Two digits
if (s.charAt(i-1) == '*' && s.charAt(i) == '*') {
temp += 15 * prev;
} else if (s.charAt(i-1) == '*') {
if (s.charAt(i) >= '0' && s.charAt(i) <= '6') {
temp += 2 * prev;
} else if (s.charAt(i) >= '7' && s.charAt(i) <= '9') {
temp += prev;
}
} else if (s.charAt(i) == '*') {
if (s.charAt(i-1) == '1') {
temp += 9 * prev;
} else if (s.charAt(i-1) == '2') {
temp += 6 * prev;
}
} else {
int two = (s.charAt(i-1) - '0') * 10 + (s.charAt(i) - '0');
if (two >= 10 && two <= 26) {
temp += prev;
}
}
temp %= MOD;
prev = curr;
curr = temp;
}
return (int)curr;
}
}
var numDecodings = function(s) {
const MOD = 1e9 + 7;
let n = s.length;
let prev = 1;
let curr = s[0] === '*' ? 9 : (s[0] === '0' ? 0 : 1);
for (let i = 1; i < n; ++i) {
let temp = 0;
// Single digit
if (s[i] === '*') {
temp += 9 * curr;
} else if (s[i] !== '0') {
temp += curr;
}
// Two digits
if (s[i-1] === '*' && s[i] === '*') {
temp += 15 * prev;
} else if (s[i-1] === '*') {
if ('0' <= s[i] && s[i] <= '6') {
temp += 2 * prev;
} else if ('7' <= s[i] && s[i] <= '9') {
temp += prev;
}
} else if (s[i] === '*') {
if (s[i-1] === '1') {
temp += 9 * prev;
} else if (s[i-1] === '2') {
temp += 6 * prev;
}
} else {
let two = parseInt(s[i-1]) * 10 + parseInt(s[i]);
if (two >= 10 && two <= 26) {
temp += prev;
}
}
temp %= MOD;
[prev, curr] = [curr, temp];
}
return curr;
};