Decode Ways

medium dp string

Problem

A message containing letters from A-Z can be encoded into numbers using the following mapping: 'A' -> "1" 'B' -> "2" ... 'Z' -> "26" To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into: "AAJF" with the grouping (1 1 10 6) "KJF" with the grouping (11 10 6) Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06". Given a string s containing only digits, return the number of ways to decode it.

Inputs = "226"

Output3

"BZ", "VF", "BBF". dp[i] = (1-digit valid ? dp[i−1] : 0) + (2-digit valid ? dp[i−2] : 0).

s (digits only)

def num_decodings(s):
    if not s or s[0] == "0":
        return 0
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = dp[1] = 1
    for i in range(2, n + 1):
        one = int(s[i - 1])
        two = int(s[i - 2:i])
        if 1 <= one <= 9:
            dp[i] += dp[i - 1]
        if 10 <= two <= 26:
            dp[i] += dp[i - 2]
    return dp[n]

function numDecodings(s) {
  if (!s || s[0] === "0") return 0;
  const n = s.length;
  const dp = new Array(n + 1).fill(0);
  dp[0] = dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    const one = Number(s[i - 1]);
    const two = Number(s.slice(i - 2, i));
    if (one >= 1 && one <= 9) dp[i] += dp[i - 1];
    if (two >= 10 && two <= 26) dp[i] += dp[i - 2];
  }
  return dp[n];
}

class Solution {
    public int numDecodings(String s) {
        if (s.isEmpty() || s.charAt(0) == '0') return 0;
        int n = s.length();
        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            int one = s.charAt(i - 1) - '0';
            int two = Integer.parseInt(s.substring(i - 2, i));
            if (one >= 1 && one <= 9) dp[i] += dp[i - 1];
            if (two >= 10 && two <= 26) dp[i] += dp[i - 2];
        }
        return dp[n];
    }
}

int numDecodings(string s) {
    if (s.empty() || s[0] == '0') return 0;
    int n = s.size();
    vector<int> dp(n + 1, 0);
    dp[0] = dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        int one = s[i - 1] - '0';
        int two = stoi(s.substr(i - 2, 2));
        if (one >= 1 && one <= 9) dp[i] += dp[i - 1];
        if (two >= 10 && two <= 26) dp[i] += dp[i - 2];
    }
    return dp[n];
}

Explanation

We are decoding a digit string where 1 means 'A' up to 26 means 'Z'. The key insight is that to decode a position, we only ever look at the last one or two digits, so a simple 1D DP works.

Let dp[i] be the number of ways to decode the first i characters. To extend, the last letter used either a single digit (the char at s[i-1], valid if it is 1..9, contributing dp[i-1]) or a two-digit code (s[i-2..i-1], valid if it is 10..26, contributing dp[i-2]).

We seed dp[0] = dp[1] = 1. The early exit for a leading '0' matters because no letter maps to 0, and codes like "06" are not allowed.

Example: s = "226". dp[1] = 1. At position 2 both "2" and "22" are valid, so dp[2] = 2. At position 3, "6" is valid (+dp[2]) and "26" is valid (+dp[1]), giving dp[3] = 2 + 1 = 3 — matching "BZ", "VF", "BBF".

Each position checks at most two small conditions, so the whole scan is linear in the length of the string.

Time: O(n) Space: O(n)