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.
1#include <string>
2#include <vector>
3
4int numDecodings(std::string s) {
5 if (s.empty() || s[0] == '0') return 0;
6 int n = s.size();
7 std::vector<int> dp(n + 1, 0);
8 dp[0] = 1;
9 dp[1] = 1;
10
11 for (int i = 2; i <= n; i++) {
12 if (s[i - 1] != '0') {
13 dp[i] += dp[i - 1];
14 }
15 int twoDigit = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
16 if (twoDigit >= 10 && twoDigit <= 26) {
17 dp[i] += dp[i - 2];
18 }
19 }
20 return dp[n];
21}The C++ solution uses a vector to maintain the number of decodings up to each index. This vector is initialized with zeros and we set the first two elements based on initial conditions.
Like the C solution, this checks for single and valid two-digit decodings and updates the vector accordingly.
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.
1var numDecodings = function(s) {
2 if (!s || s[0] === '0') return 0;
3 let n = s.length;
4 let prev1 = 1, prev2 = 1;
5
6 for (let i = 1; i < n; i++) {
7 let current = 0;
8 let oneDigit = parseInt(s[i]);
9 let twoDigits = parseInt(s.slice(i - 1, i + 1));
10
11 if (oneDigit >= 1) {
12 current += prev1;
13 }
14 if (twoDigits >= 10 && twoDigits <= 26) {
15 current += prev2;
16 }
17 prev2 = prev1;
18 prev1 = current;
19 }
20 return prev1;
21};Javascript highlights constant space through in-place intermediate solution derivation, utilizing functionally efficient constructs making for minimal temporal overhead.
By storing only essential data, it’s possible to capture extensive stride potential while maintaining check upon memory adoption.