The dynamic programming approach leverages the fact that a problem can be broken into subproblems. Here, we use an array dp where dp[i] represents the number of ways to decode the substring s[0..i-1].
We iterate through the string and update the dp array based on the valid single and two-digit mappings.
Time Complexity: O(n), where n is the length of the input string. This is because we iterate over each character once.
Space Complexity: O(n), as we use an additional array of size n for storing our results for subproblems.
1using System;
2
3public class Solution {
4 public int NumDecodings(string s) {
5 if (s == null || s.Length == 0 || s[0] == '0') return 0;
6
7 int n = s.Length;
8 int[] dp = new int[n + 1];
9 dp[0] = 1;
10 dp[1] = 1;
11
12 for (int i = 2; i <= n; i++) {
13 int oneDigit = int.Parse(s.Substring(i - 1, 1));
14 int twoDigits = int.Parse(s.Substring(i - 2, 2));
15
16 if (oneDigit >= 1) {
17 dp[i] += dp[i - 1];
18 }
19 if (twoDigits >= 10 && twoDigits <= 26) {
20 dp[i] += dp[i - 2];
21 }
22 }
23 return dp[n];
24 }
25}This C# solution employs similar logic to other solutions, scanning the string and calculating using an array for dynamic programming.
The type-safe nature of C# ensures clear handling of string slicing and integer parsing operations.
Instead of using an entire array to store all previous results, this approach keeps track of only the last two computations (since we only ever need the last two values for our dp computations).
Thus, we use two variables to hold these values and update them as needed to keep our space usage minimal.
Time Complexity: O(n), since each character in the string is touched once.
Space Complexity: O(1), because only two variables are used to maintain state.
1class Solution:
2 def numDecodings(self, s: str) -> int:
3 if not s or s[0] == '0':
4 return 0
5
6 n = len(s)
7 prev1, prev2 = 1, 1
8
9 for i in range(1, n):
10 current = 0
11 one_digit = int(s[i])
12 two_digits = int(s[i-1:i+1])
13
14 if 1 <= one_digit <= 9:
15 current += prev1
16 if 10 <= two_digits <= 26:
17 current += prev2
18
19 prev2 = prev1
20 prev1 = current
21
22 return prev1Utilizing Python's intuitive dynamic nature, two variables maintain preceding results to support ongoing calculations without resorting to expansive memory utilization.
Holding results to adjacent indices allow dynamic inter-update operations with a fixed space guarantee.