Decode Ways: Unraveling Encoded Messages with Dynamic Programming

The "Decode Ways" problem is a dynamic programming challenge that revolves around decoding a string of digits into alphabets, akin to the way messages were encoded in the past.

Problem Statement

Given a string s containing only digits, return the number of ways to decode it into letters using the mapping: '1' -> 'A', '2' -> 'B', ..., '26' -> 'Z'.

Example

• Input: s = "12" Output: 2 Explanation: It could be decoded as "AB" (1 2) or "L" (12).

• Input: s = "226" Output: 3 Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Dynamic Programming Solution

function numDecodings(s) {
  if (s[0] === "0") return 0;
  let dp = new Array(s.length + 1).fill(0);
  dp[0] = 1;
  dp[1] = 1;

  for (let i = 2; i <= s.length; i++) {
    let oneDigit = parseInt(s.slice(i - 1, i));
    let twoDigits = parseInt(s.slice(i - 2, i));

    if (oneDigit >= 1) {
      dp[i] += dp[i - 1];
    }
    if (twoDigits >= 10 && twoDigits <= 26) {
      dp[i] += dp[i - 2];
    }
  }

  return dp[s.length];
}

Breaking Down the Solution

• Handle Leading Zero: If the string starts with '0', return 0, as it can't be decoded.
• Initialize dp Array: Create a dp array to store the number of ways to decode up to each character in the string.
• Iterate and Update dp: For each character, check if it forms a valid one-digit or two-digit number and update dp accordingly.
• Return Decoding Count: The last element in the dp array gives the total number of ways to decode the entire string.

Conclusion

The Decode Ways problem is an interesting application of dynamic programming in string processing. It showcases how to approach problems where solutions depend on the number of ways previous subproblems have been solved, illustrating the flexibility and utility of dynamic programming in a wide range of scenarios.