decode-ways.ts

/**
 * 91. Decode Ways  (Medium)
 * Link: https://leetcode.com/problems/decode-ways/
 *
 * A message of digits is encoded with 'A'->"1" ... 'Z'->"26". Return the number
 * of ways to decode the string. Leading zeros make a grouping invalid (e.g.
 * "06" is not a valid encoding of 6).
 *
 * Example:
 *   Input:  s = "226"
 *   Output: 3            // "BZ" (2 26), "VF" (22 6), "BBF" (2 2 6)
 *
 * Approach:
 *   1-D DP like Fibonacci. dp[i] = ways to decode the first i characters. A new
 *   digit s[i-1] adds dp[i-1] ways if it is 1..9; the pair s[i-2..i] adds
 *   dp[i-2] ways if it forms 10..26. Keep only the two previous counts.
 *
 * Time:  O(n)
 * Space: O(1)
 */
export function numDecodings(s: string): number {
  if (s.length === 0 || s[0] === "0") return 0;

  let twoBack = 1; // dp[0]
  let oneBack = 1; // dp[1]

  for (let i = 1; i < s.length; i++) {
    let current = 0;
    if (s[i] !== "0") current += oneBack; // single digit 1..9

    const twoDigit = Number(s.slice(i - 1, i + 1));
    if (twoDigit >= 10 && twoDigit <= 26) current += twoBack;

    twoBack = oneBack;
    oneBack = current;
  }

  return oneBack;
}