{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Decode Ways – Solution & Complexity

Interview solutions
/
Decode Ways

Solution Walkthrough

  1. Step 1: Define the suffix state

    • The choice at index i only affects the remaining suffix after consuming one or two digits.
    • That makes this a natural dynamic-programming problem over suffixes.

  2. Step 2: Brute-force baseline

    • A recursive search tries one-digit and two-digit decodes whenever they are valid.
    • Without memoization, repeated suffixes explode exponentially.

  3. Step 3: Rolling DP transition

    • If s[i] is 0, there are 0 ways from that position.
    • Otherwise, start with the number of ways from i + 1 (taking one digit).
    • If s[i:i+2] is between 10 and 26, also add the number of ways from i + 2.

  4. Step 4: Final solution (all languages)

    A right-to-left scan only needs the next two DP values, so the suffix DP compresses to constant space.

    def num_decodings(s: str) -> int:
    next_one = 1
    next_two = 1

    for i in range(len(s) - 1, -1, -1):
        if s[i] == '0':
            current = 0
        else:
            current = next_one
            if i + 1 < len(s) and (s[i] == '1' or (s[i] == '2' and s[i + 1] <= '6')):
                current += next_two

        next_two = next_one
        next_one = current

    return next_one

  5. Step 5: Common mistakes and follow-ups

    • Treating 0 as a standalone letter, which is never allowed.
    • Allowing any two-digit number under 30; only 10 through 26 are valid pairs.
    • Follow-up: when * is introduced, the recurrence stays similar but each branch contributes multiple counts instead of just one.

FAQ

See also

Practice Decode Ways online (run code in the browser)Edit Distance solution (hard)Longest Common Subsequence solution (medium)Longest Palindromic Substring solution (medium)Longest Valid Parentheses solution (hard)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?