1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
/**
 * Recursive approach (brute force)
 * Time Complexity: O(2^n) - Exponential in worst case
 * Space Complexity: O(n) - Recursion stack
 * 
 * @param {string} s - The encoded message
 * @return {number} - Number of ways to decode
 */
function numDecodingsRecursive(s) {
  // Base case: empty string has 1 way to decode
  if (s.length === 0) {
    return 1;
  }
  
  // If the string starts with '0', it cannot be decoded
  if (s[0] === '0') {
    return 0;
  }
  
  // Initialize result
  let ways = 0;
  
  // Option 1: Take a single digit
  ways += numDecodingsRecursive(s.substring(1));
  
  // Option 2: Take two digits if valid
  if (s.length >= 2) {
    const twoDigits = parseInt(s.substring(0, 2));
    if (twoDigits >= 10 && twoDigits <= 26) {
      ways += numDecodingsRecursive(s.substring(2));
    }
  }
  
  return ways;
}
 
/**
 * Memoization approach (top-down dynamic programming)
 * Time Complexity: O(n) - Each position is processed once
 * Space Complexity: O(n) - For memoization and recursion stack
 * 
 * @param {string} s - The encoded message
 * @return {number} - Number of ways to decode
 */
function numDecodingsMemo(s) {
  const memo = new Map();
  
  function decode(index) {
    // Base case: reached the end of the string
    if (index === s.length) {
      return 1;
    }
    
    // If already computed, return from memo
    if (memo.has(index)) {
      return memo.get(index);
    }
    
    // If current digit is '0', it cannot be decoded on its own
    if (s[index] === '0') {
      return 0;
    }
    
    // Option 1: Take a single digit
    let ways = decode(index + 1);
    
    // Option 2: Take two digits if valid
    if (index + 1 < s.length) {
      const twoDigits = parseInt(s.substring(index, index + 2));
      if (twoDigits >= 10 && twoDigits <= 26) {
        ways += decode(index + 2);
      }
    }
    
    // Store result in memo
    memo.set(index, ways);
    return ways;
  }
  
  return decode(0);
}
 
/**
 * Tabulation approach (bottom-up dynamic programming)
 * Time Complexity: O(n) - Each position is processed once
 * Space Complexity: O(n) - For the DP array
 * 
 * @param {string} s - The encoded message
 * @return {number} - Number of ways to decode
 */
function numDecodingsDP(s) {
  const n = s.length;
  
  // Edge case: empty string
  if (n === 0) return 0;
  
  // Create DP array
  const dp = new Array(n + 1).fill(0);
  
  // Base case: empty string has 1 way to decode
  dp[n] = 1;
  
  // Fill DP array from right to left
  for (let i = n - 1; i >= 0; i--) {
    // If current digit is '0', it cannot be decoded on its own
    if (s[i] === '0') {
      dp[i] = 0;
    } else {
      // Option 1: Take a single digit
      dp[i] = dp[i + 1];
      
      // Option 2: Take two digits if valid
      if (i + 1 < n) {
        const twoDigits = parseInt(s.substring(i, i + 2));
        if (twoDigits >= 10 && twoDigits <= 26) {
          dp[i] += dp[i + 2];
        }
      }
    }
  }
  
  return dp[0];
}
 
/**
 * Optimized space complexity approach
 * Time Complexity: O(n) - Each position is processed once
 * Space Complexity: O(1) - Constant extra space
 * 
 * @param {string} s - The encoded message
 * @return {number} - Number of ways to decode
 */
function numDecodings(s) {
  const n = s.length;
  
  // Edge case: empty string
  if (n === 0) return 0;
  
  // Initialize variables for DP[i+1] and DP[i+2]
  let dp1 = 1; // DP[n]
  let dp2 = 0; // Placeholder
  
  // Iterate from right to left
  for (let i = n - 1; i >= 0; i--) {
    // Initialize current DP value
    let current = 0;
    
    // If current digit is not '0', it can be decoded on its own
    if (s[i] !== '0') {
      current = dp1;
    }
    
    // Check if two digits can be decoded together
    if (i + 1 < n) {
      const twoDigits = parseInt(s.substring(i, i + 2));
      if (twoDigits >= 10 && twoDigits <= 26) {
        current += dp2;
      }
    }
    
    // Update variables for next iteration
    dp2 = dp1;
    dp1 = current;
  }
  
  return dp1;
}
 
// Test cases
console.log(numDecodings("12"));     // 2
console.log(numDecodings("226"));    // 3
console.log(numDecodings("06"));     // 0
console.log(numDecodings("10"));     // 1
console.log(numDecodings("27"));     // 1
console.log(numDecodings("2101"));   // 1