How do you solve Decode Ways?

Use a top-down recursive function with memoization. The function dp(i) returns the number of decoding ways starting at index i. If s[i] is '0', return 0 immediately. Otherwise, sum dp(i+1) and dp(i+2) if the two-digit number s[i:i+2] is valid (<= 26). Store results in a memo dictionary keyed by index to ensure each subproblem is solved once. Return dp(0) as the final answer.

What pattern does Decode Ways use?

The Pattern: Dynamic Programming (Top-Down Memoization) The Heuristic: When counting ways to decode or partition sequences with overlapping subproblems, use recursion with memoization to cache intermediate results, transforming exponential brute-force into efficient linear-time solutions.

Decode Ways — Dynamic Programming

Q: What is the time complexity of Decode Ways?

O(n). Each index in the string is computed once and stored in the memo dictionary. Each recursive call does O(1) work aside from recursive calls, resulting in linear time relative to the string length.

Q: What pattern does Decode Ways use?

The Pattern: Dynamic Programming (Top-Down Memoization) The Heuristic: When counting ways to decode or partition sequences with overlapping subproblems, use recursion with memoization to cache intermediate results, transforming exponential brute-force into efficient linear-time solutions.

Problem

Given a string s containing only digits, return the number of ways to decode it according to the mapping 'A'->1, 'B'->2, ..., 'Z'->26.

1 ≤ s.length ≤ 100
s contains only digits and may contain leading zeros

Example

Input: s = "226"

Output: 3

The string "226" can be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6). The algorithm uses recursion with memoization to count all valid decoding paths. Starting at index 0, it explores decoding one digit ('2') and then two digits ('22') if valid. It sums the counts from these recursive calls, caching results to avoid redundant computations. The critical moment is recognizing that '0' cannot be decoded alone, so paths starting with '0' return 0 immediately, pruning invalid branches.

Approach

Straightforward Solution

A brute-force recursive approach tries all possible decoding splits without caching, leading to exponential time due to overlapping subproblems and repeated computations.

Core Observation

Each position in the string can be decoded either as a single digit (if not '0') or as a valid two-digit number between 10 and 26. The total decoding ways from a position equals the sum of decoding ways from the next position and, if valid, from the position after next.

Path to Optimal

Preview

The key recognition signals are 'count number of ways', 'string of digits', and 'mapping 1 to 26'. These indicate Dynamic Programming because the problem breaks down into overlapping subproblems where the solution at index i depends on solutions at i+1 and i+2…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a top-down recursive function with memoization. The function dp(i) returns the number of decoding ways starting at index i…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each index in the string is computed once and stored in the memo dictionary. Each recursive call does O(1) work aside from recursive calls, resulting in linear time relative to the string length.

Space

O(n)

The memo dictionary stores results for each index, requiring O(n) auxiliary space. The recursion stack depth is at most n, also contributing O(n) space.

Solution

Python

1class Solution:
  def numDecodings(self, s: str) -> int:
      memo = { len(s): 1 }
4
      def dp(i):
          if i in memo:
              return memo[i]
          if s[i] == "0":
              return 0
          
          res = dp(i + 1)
          if (i + 1 < len(s) and (s[i] == "1" or 
             (s[i] == "2" and s[i + 1] in "0123456"))):
              res += dp(i + 2)
          
          memo[i] = res
          return res
      
      return dp(0)

Step-by-Step Solution

1

Initialize Memoization Cache with Base Case

3	`memo = { len(s): 1 }`

Objective

To set up a memo dictionary with a base case indicating that decoding beyond the last character counts as one valid way.

Key Insight

Initializing memo with the base case at index len(s) = 1 represents the empty substring after the end of the string, which counts as one valid decoding path. This base case anchors the recursion and allows dp(i) to return 1 when it reaches the end, enabling correct accumulation of decoding counts.

Interview Quick-Check

Core Logic

The memo dictionary caches results for each index, with the base case memo[len(s)] = 1 representing a successful decoding path beyond the string.

State & Boundaries

The base case ensures recursion terminates correctly when the index reaches the string length.

2

Recursively Compute Decoding Ways with Memoization

To recursively calculate the number of decoding ways starting at index i, using memoization to avoid redundant computations.

3

Return Total Decoding Ways from Start of String

To initiate the recursive decoding count from index 0 and return the total number of valid decoding ways for the entire string.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 5 Critical lines interviewers watch for.

Line 6 Critical

if i in memo:

Return cached result if index i has been computed before.

Memoization lookup prevents redundant recursive calls, reducing exponential time complexity to linear by reusing previously computed results.

Line 7 Critical

return memo[i]

Return memoized decoding count for index i.

Returning the cached value immediately ensures efficient reuse of computed subproblem results.

Line 8 Critical

if s[i] == "0":

Return 0 if current character is '0', as it cannot be decoded alone.

This early pruning is critical to correctness, as '0' digits do not map to any letter and invalidate decoding paths starting here.

Full line-by-line criticality + rationale for all 13 lines available on Pro.

Test Your Understanding

Why must the algorithm return 0 immediately when encountering a '0' digit at the current index?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Decode Ways from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Decode Ways drill

or drill a free problem

1	`class Solution:`
2	`def numDecodings(self, s: str) -> int:`
3	`memo = { len(s): 1 }`
4
5	`def dp(i):`
6	`if i in memo:`
7	`return memo[i]`
8	`if s[i] == "0":`
9	`return 0`
10
11	`res = dp(i + 1)`
12	`if (i + 1 < len(s) and (s[i] == "1" or`
13	`(s[i] == "2" and s[i + 1] in "0123456"))):`
14	`res += dp(i + 2)`
15
16	`memo[i] = res`
17	`return res`
18
19	`return dp(0)`