Sponsored
Sponsored
This approach utilizes a dynamic programming (DP) technique to solve the problem. We define a DP array where dp[i] represents the number of ways to decode the substring of length i. We iterate through the string, updating the DP array based on the current character and its possible pairings with the previous character.
Time Complexity: O(n), where n is the length of the input string.
Space Complexity: O(n), due to the dynamic programming array used.
1public class Solution {
2 public int numDecodings(String s) {
3 int MOD = 1000000007;
4 int n = s.length();
5 if (n == 0) return 0;
6
7 long[] dp = new long[n + 1];
8 dp[0] = 1;
9 dp[1] = s.charAt(0) == '*' ? 9 : s.charAt(0) != '0' ? 1 : 0;
10
11 for (int i = 2; i <= n; i++) {
12 char first = s.charAt(i - 1);
13 char second = s.charAt(i - 2);
14
15 if (first == '*') {
16 dp[i] += 9 * dp[i - 1];
17 } else if (first != '0') {
18 dp[i] += dp[i - 1];
19 }
20
21 if (second == '*') {
22 if (first == '*') {
23 dp[i] += 15 * dp[i - 2];
24 } else if (first <= '6') {
25 dp[i] += 2 * dp[i - 2];
26 } else {
27 dp[i] += dp[i - 2];
28 }
29 } else if (second == '1') {
30 if (first == '*') {
31 dp[i] += 9 * dp[i - 2];
32 } else {
33 dp[i] += dp[i - 2];
34 }
35 } else if (second == '2') {
36 if (first == '*') {
37 dp[i] += 6 * dp[i - 2];
38 } else if (first <= '6') {
39 dp[i] += dp[i - 2];
40 }
41 }
42
43 dp[i] %= MOD;
44 }
45
46 return (int) dp[n];
47 }
48}This solution follows a similar dynamic programming logic as the Python solution. The dp array is initialized to store decoding ways for substring lengths up to n. Each character is evaluated for both single and pair encodings, incorporating multiple possibilities thanks to '*'. Each calculation respects modulo 10^9 + 7.
This is a space-optimized version of the dynamic programming solution. Instead of using a full dp array, we keep track of only the last two states needed, thereby reducing space complexity.
Time Complexity: O(n), where n is the length of the input string.
Space Complexity: O(1), as we use only constant extra space.
1function numDecodings(s) {
2 const MOD
This JavaScript solution is similarly optimized in terms of space, using only two variables to track the last two relevant decoding states. It follows dynamic programming principles while using inline conditions to handle single characters and pairs efficiently.