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.
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.