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.
1def numDecodings(s: str) -> int:
2 MOD = 10**9 + 7
3 n = len(s)
4 if n == 0:
5 return 0
6
7 dp = [0] * (n + 1)
8 dp[0] = 1
9
10 if s[0] == '*':
11 dp[1] = 9
12 elif s[0] != '0':
13 dp[1] = 1
14
15 for i in range(2, n + 1):
16
17 first = s[i-1]
18 second = s[i-2]
19
20 if first == '*':
21 dp[i] = 9 * dp[i-1]
22 elif first != '0':
23 dp[i] = dp[i-1]
24
25 if second == '*':
26 if first == '*':
27 dp[i] = (dp[i] + 15 * dp[i-2]) % MOD
28 elif '0' <= first <= '6':
29 dp[i] = (dp[i] + 2 * dp[i-2]) % MOD
30 else:
31 dp[i] = (dp[i] + dp[i-2]) % MOD
32 elif second == '1':
33 if first == '*':
34 dp[i] = (dp[i] + 9 * dp[i-2]) % MOD
35 else:
36 dp[i] = (dp[i] + dp[i-2]) % MOD
37 elif second == '2':
38 if first == '*':
39 dp[i] = (dp[i] + 6 * dp[i-2]) % MOD
40 elif '0' <= first <= '6':
41 dp[i] = (dp[i] + dp[i-2]) % MOD
42
43 return dp[n] % MODThis solution introduces a dynamic programming approach. The dp[i] array stores the number of decoding ways for the substring up to the ith character. The initial state is set based on the first character, considering '.' as all digits 1-9. Each subsequent character adjusts dp[i] depending on its value and the preceding character(s), also accounting for the '*' possibilities. All computations are done modulo 10^9 + 7 to limit overflow.
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.
1#include <string.h>
2
3#define
This C solution optimizes space by maintaining only two integer variables, prev and curr, to store results of the previous and current positions respectively. This replaces the need for an entire dp array, reducing space usage while maintaining the dynamic programming logic.