MediumDynamic Programming

Decode Ways

Letters are encoded as numbers: A → 1, B → 2, …, Z → 26. Given a string s of digits, return the number of ways to group the digits back into letters. A group can't have a leading zero, so "01" is not a letter.

s = "12" → 2 ("AB", "L")s = "01" → 0"1012" → "JAB", "JL"

Try:
CALL
1 / 1

Code

The highlighted line runs next. The pill shows the live values in the running call.

Variables

The data structures the code is building

The digits

Number above each digit = ways to decode from there to the end

Time and space complexity

n = len(s). The highlighted row is the solution being traced.

Keyboard: ← → step, Space play or pause. Digits only; drawings use at most 7 digits for plain recursion, 10 for top-down and 14 for the loops.