☕ DSA Java Articles

Topics › Dynamic Programming › 1D DP

Decode Ways

Easy TUF ID 2397 Blind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

A message of capital letters is encoded with 'A' → "1", 'B' → "2", …, 'Z' → "26". Given a string s of digits, return the number of different ways to decode it back into letters. Every digit must be used, and a code never has a leading zero: "06" is not a way to write 'F'. If the string cannot be decoded at all, the answer is 0.

Constraints: 1 ≤ s.length ≤ 100, s contains only digits (possibly with leading zeros), and the answer fits in a 32-bit signed integer.

Example 1

s = "226"
answer = 3          // "2 2 6" = BBF, "22 6" = VF, "2 26" = BZ

Example 2

s = "06"
answer = 0          // no code starts with 0, and "06" is not "6"

Example 3

s = "11106"
answer = 2          // "1 1 10 6" = AAJF and "11 10 6" = KJF; "1 11 06" is invalid

Every approach uses one small helper. Given that s[i] is not '0', it tells whether s[i] and s[i + 1] together form a valid two-digit code, which means a value between 10 and 26:

static boolean twoDigitCode(String s, int i) {
    return i + 1 < s.length() && (s.charAt(i) - '0') * 10 + (s.charAt(i + 1) - '0') <= 26;
}

Approach 1: Recursion

Intuition. Decode from left to right. At position i, the next letter uses either one digit or two digits:

Each valid choice leaves a shorter suffix to decode, and the two choices produce different decodings, so the counts add up:

ways(i) = ways(i + 1) + (two-digit code valid ? ways(i + 2) : 0), and ways(i) = 0 if s[i] == '0'.

The base case ways(n) = 1 says that once every digit is used, we have found exactly one complete decoding. A '0' can never start a code; it is only ever consumed as the second digit of 10 or 20, through the two-digit choice at the position before it.

Algorithm.

  1. If i == n, return 1.
  2. If s[i] == '0', return 0.
  3. Return solve(i + 1), plus solve(i + 2) when the two-digit code is valid.
static int recursion(String s) {
    return solve(0, s);
}

static int solve(int i, String s) {
    if (i == s.length()) return 1;                         // consumed everything: one complete decoding
    if (s.charAt(i) == '0') return 0;                      // no code starts with 0
    int ways = solve(i + 1, s);
    if (twoDigitCode(s, i)) ways += solve(i + 2, s);
    return ways;
}

Complexity. Time exponential: for a string of 1s the call tree grows like the Fibonacci numbers, about 1.6^n calls. Space O(n) for the recursion stack.

Approach 2: Memoization

Intuition. solve(i) depends only on i, and there are only n + 1 different suffixes. The recursion recomputes them constantly: solve(3) is reached both through 1 → 2 → 3 and through 1 → 3. Caching each result in memo[i] makes every suffix cost O(1) after its first visit. The answer is never negative, so -1 marks “not computed”.

static int memoization(String s) {
    int[] memo = new int[s.length() + 1];
    Arrays.fill(memo, -1);
    return solveMemo(0, s, memo);
}

static int solveMemo(int i, String s, int[] memo) {
    if (i == s.length()) return 1;
    if (s.charAt(i) == '0') return 0;
    if (memo[i] != -1) return memo[i];
    int ways = solveMemo(i + 1, s, memo);
    if (twoDigitCode(s, i)) ways += solveMemo(i + 2, s, memo);
    return memo[i] = ways;
}

Complexity. Time O(n), space O(n) for the memo plus O(n) stack.

Approach 3: Tabulation

Intuition. Turn the recursion around and fill dp[i] = number of ways to decode the suffix starting at i, from right to left. dp[n] = 1 is the empty suffix. Each dp[i] reads only dp[i + 1] and dp[i + 2], which are already filled.

Algorithm.

  1. dp[n] = 1.
  2. For i = n - 1 down to 0: if s[i] == '0', leave dp[i] = 0. Otherwise dp[i] = dp[i + 1], plus dp[i + 2] if the two-digit code is valid.
  3. Return dp[0].

When twoDigitCode is true, i + 1 < n, so dp[i + 2] is at most dp[n] and always inside the array.

static int tabulation(String s) {
    int n = s.length();
    int[] dp = new int[n + 1];
    dp[n] = 1;                                             // the empty suffix has exactly one decoding
    for (int i = n - 1; i >= 0; i--) {
        if (s.charAt(i) == '0') continue;                  // dp[i] stays 0
        dp[i] = dp[i + 1];
        if (twoDigitCode(s, i)) dp[i] += dp[i + 2];
    }
    return dp[0];
}

Dry run on Example 3, s = "11106" (n = 5):

i s[i] one digit two digits dp[i]
5 end     1
4 6 dp[5] = 1 no next digit 1
3 0 not allowed not allowed 0
2 1 dp[3] = 0 “10” valid: dp[4] = 1 1
1 1 dp[2] = 1 “11” valid: dp[3] = 0 1
0 1 dp[1] = 1 “11” valid: dp[2] = 1 2

The zero at index 3 makes dp[3] = 0, so any decoding that would start a code at that 0 contributes nothing. The only way past it is the two-digit code "10" from index 2.

Complexity. Time O(n), space O(n).

Approach 4: Space optimised

Intuition. dp[i] needs only the next two values, so two variables are enough: next1 = dp[i + 1] and next2 = dp[i + 2]. Start with next1 = dp[n] = 1 and next2 = 0. The 0 is never actually read at i = n - 1, because there is no second digit there. After computing cur, shift both variables one step left. This is the same rolling pattern as Fibonacci or climbing stairs; for a string of all 1s the answer is a Fibonacci number.

static int spaceOptimised(String s) {
    int next1 = 1, next2 = 0;                              // next1 = dp[i + 1], next2 = dp[i + 2]
    for (int i = s.length() - 1; i >= 0; i--) {
        int cur = 0;
        if (s.charAt(i) != '0') {
            cur = next1;
            if (twoDigitCode(s, i)) cur += next2;
        }
        next2 = next1;
        next1 = cur;
    }
    return next1;
}

Complexity. Time O(n), space O(1).

Edge cases and pitfalls