Decoding Ways Using Backtracking and Dynamic Programming
In this blog post, we will discuss a problem that involves determining the number of ways a string of digits can be decoded into letters. This is a wellknown problem, often referred to as the “Decode Ways” problem, where each digit or pair of digits is mapped to a letter (e.g., 1 = ‘A’, 2 = ‘B’, …, 26 = ‘Z’).
We will first approach the solution using backtracking (recursion), which gives us insight into how we can further optimize the solution with dynamic programming. The accompanying image represents a recursive tree, showing different function calls and how the problem branches.
Part 1: Backtracking Approach
Problem Statement:
Given a string of digits (for example, “226”), determine how many ways it can be decoded into letters. The rules are:
 Each digit from 19 can map to a letter (‘A’ to ‘I’).
 Each twodigit number from 1026 can map to letters (‘J’ to ‘Z’).
Backtracking:
The simplest way to solve the problem is by using a recursive backtracking approach. The idea is to make choices at each step:
 Decode one digit (which must be between 1 and 9).
 Decode two digits (which must be between 10 and 26).
Each recursive call represents a decision, either taking one digit or two digits, until you reach the end of the string. If a valid decoding is reached, it’s counted as one way.
Here is the Javascript for the backtracking approach:
function decodeWays(s) {
function backtrack(index) {
if (index === s.length) return 1;
if (s[index] === '0') return 0; // Invalid starting character
let count = 0;
// Single digit decoding
count += backtrack(index + 1);
// Two digits decoding
if (index < s.length  1 && (s[index] === '1'  (s[index] === '2' && s[index + 1] <= '6'))) {
count += backtrack(index + 2);
}
return count;
}
return backtrack(0);
}
In this approach:

We recursively explore both options (one digit or two digits) at each step.

The base case is when the index reaches the end of the string, meaning we have successfully decoded it.
The image represents the recursive tree structure for the backtracking approach. Each node in the tree represents a call to the functiondecodeWays(n, index)
: 
Root Node: The root represents the original string “226”.

Branches: Each node branches into two paths:
 Taking one digit and making a recursive call for the remaining string.
 Taking two digits (if valid) and making a recursive call for the remaining string.
The arrows in the tree show the flow of recursion, while the return values are shown as numbers on the edges (e.g., 1, 2, etc.). The image highlights how the same subproblems are recomputed, which motivates us to optimize the approach using dynamic programming.
Analysis of Backtracking:
Backtracking is simple but highly inefficient, as it generates many overlapping subproblems. The tree shown in the image demonstrates how different paths (like decodeWays(226, 1)
and decodeWays(226, 2)
) are repeatedly computed, leading to exponential time complexity, specifically $O(2n)O(2^n)O(2n)$ for a string of length nnn.
Part 2: Optimization with Dynamic Programming
Dynamic Programming (DP) Approach:
To optimize the backtracking approach, we observe that the same subproblems are being solved multiple times. For example, the recursive calls decodeWays(226, 1)
and decodeWays(226, 2)
are made multiple times with the same arguments. Dynamic programming helps in avoiding this redundancy by storing the results of already solved subproblems.
We can implement a bottomup dynamic programming solution, where we store the number of ways to decode the string from index iii to the end. The idea is to build the solution starting from the end of the string and moving backward.
Here’s how we can approach it:
 Define a DP array where
dp[i]
represents the number of ways to decode the substring starting at index iii.  Initialize:
dp[n] = 1
(there is exactly one way to decode an empty string).  For each index iii from n−1n1n−1 to 0:
 If the digit at iii is ‘0’, set
dp[i] = 0
(no valid decoding).  Otherwise, set
dp[i] = dp[i+1]
(decoding the single digit).  If the twodigit number formed by s[i]s[i]s[i] and s[i+1]s[i+1]s[i+1] is between 10 and 26, add
dp[i+2]
todp[i]
.
 If the digit at iii is ‘0’, set
Here’s the dynamic programming code:
function decodeWaysDP(s) {
if (!s  s[0] === '0') return 0;
const n = s.length;
const dp = Array(n + 1).fill(0);
dp[0] = 1; // Base case: An empty string has one way to be decoded
dp[1] = s[0] !== '0' ? 1 : 0; // Base case: Single character string
for (let i = 2; i <= n; i++) {
const oneDigit = s.substring(i  1, i);
const twoDigits = s.substring(i  2, i);
// Check onedigit decode
if (oneDigit >= '1' && oneDigit <= '9') {
dp[i] += dp[i  1];
}
// Check twodigit decode
if (twoDigits >= '10' && twoDigits <= '26') {
dp[i] += dp[i  2];
}
}
return dp[n];
}
Time and Space Complexity:
 Time Complexity:$O(n)O(n)O(n)$, where nnn is the length of the string. We only process each character once.
 Space Complexity: $O(n)O(n)O(n)$ because of the DP array. However, we can further optimize the space to $O(1)O(1)O(1)$ by only keeping track of the last two states.
Memoization (TopDown) Approach:
If you prefer a recursive solution but want the efficiency of dynamic programming, you can use memoization. Here, instead of solving each subproblem multiple times, we store the results of the subproblems in a cache, avoiding redundant calculations.
Conclusion
Backtracking provides an intuitive way to solve the problem but leads to redundant calculations and inefficiency. By leveraging dynamic programming, we can optimize the solution to run in linear time. Understanding the recursive tree helps in visualizing the problem’s structure, making it easier to comprehend how dynamic programming improves performance.