Decode Ways

Medium20–25 min

Topics

Dynamic ProgrammingString

Companies

FacebookAmazonMicrosoft

A message made up only of the digits 1-9 was encoded by mapping 'A' to "1", 'B' to "2", all the way up to 'Z' being "26" — so a decoded letter can come from either a single digit (1-9) or a pair of digits read together (10-26). Given the encoded digit string, count how many distinct ways it can be decoded back into letters. A '0' can never stand for a letter on its own, so it's only ever valid as the second digit of a two-digit pairing. Every position in the string faces the same choice as the one before it: read the current digit as its own letter and move one step forward, or — if it pairs with the next digit to form a number from 10 to 26 — read the two together as one letter and move two steps forward. Both choices, when valid, contribute their own count of ways to finish decoding the rest of the string, and adding those counts together gives the total ways to decode from the current position onward. Building this up from the front of the string, one position at a time, turns what would otherwise be an exponential branching search into a single linear pass.

Test Case 1:

Input:s = "15"

Output:2

Explanation:Two readings: "1","5" (A, E) or "15" (O) — 2 ways.

Test Case 2:

Input:s = "1123"

Output:5

Explanation:Five readings, splitting into one- and two-digit groups every way that keeps each group in range 1-26.

Test Case 3:

Input:s = "2611"

Output:4

Explanation:Four readings: "2","6","1","1"; "26","1","1"; "2","6","11"; "26","11".

Constraints

◆1 ≤ s.length ≤ 100
◆s consists of digits only ('0'-'9')

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

A digit string maps to letters A-Z (1-26) by grouping consecutive digits either one at a time or two at a time, and a '0' can only ever appear as the second digit of a valid two-digit group (since there's no letter for 0). Starting from the front of the string, the number of ways to decode the rest is the number of ways starting one digit later (treating the current digit alone) plus, when the next two digits together form a valid letter (10-26), the number of ways starting two digits later. Reaching the end of the string cleanly counts as exactly one valid decoding, and hitting a lone '0' that can't be grouped kills that entire branch.

TimeO(2^n)

SpaceO(n)

Java

Try it out

class Solution {
    private String s;

    public int decodeWays(String s) {
        this.s = s;
        return solve(0);
    }

    private int solve(int i) {
        int n = s.length();
        if (i == n) return 1;
        if (s.charAt(i) == '0') return 0;
        int ways = solve(i + 1);
        if (i + 1 < n) {
            int twoDigit = (s.charAt(i) - '0') * 10 + (s.charAt(i + 1) - '0');
            if (twoDigit <= 26) ways += solve(i + 2);
        }
        return ways;
    }
}

Optimal — Bottom-Up 1D DP

Optimal

Instead of recursing from the front, build up the number of ways to decode each prefix of the string from the empty prefix onward. dp[i] holds the number of ways to decode the first i characters; the empty prefix and the first character (when it isn't '0') each count as exactly one way to start. For every later position, the last single digit contributes dp[i-1] ways whenever it's non-zero on its own, and the last two digits together contribute dp[i-2] ways whenever they form a number from 10 to 26 — adding both contributions gives dp[i], and the final entry holds the answer for the whole string.

TimeO(n)