Introduction

The Decode Ways problem is one of the most important String Dynamic Programming interview questions.

Mapping:

1 -> A2 -> B
3 -> C
...
26 -> Z

Goal:

Find the number of ways to decode the string.

Example

s = "226"Output = 3

Possible Decodings:

2 2 6 = BBF22 6 = VF
2 26 = BZ

Answer:

3

Constraints

 1 <= s.length <= 100

Key Observation

At every position:

Choice 1

Take one digit:

2 → B

Choice 2

Take two digits:

22 → V

Therefore:

dp[i] = dp[i+1] + dp[i+2]

when both choices are valid.

Approach : Dynamic Programming

Explanation

For each index:

  1. Decode one digit.
  2. Decode two digits.
  3. Add valid possibilities.
  4. Store result.

Dry Run

Input:

s = "226"

Start from right:

dp[3] = 1dp[2] = 1
dp[1] = dp[2] + dp[3] = 2
dp[0] = dp[1] + dp[2] = 3

Answer:

3

Practice

Complexity Analysis

MemoizationTime Complexity: O(n)
Space Complexity: O(n)

Tabulation
Time Complexity: O(n)
Space Complexity: O(n)

Space Optimized DP
Time Complexity: O(n)
Space Complexity: O(1)

Why This Problem is Important

This problem teaches:

  • String DP
  • State Transitions
  • Multiple Choices
  • Memoization
  • Tabulation

Common Beginner Mistakes

  • Ignoring '0'
  • Invalid two-digit numbers
  • Wrong base cases
  • Not checking bounds
  • Incorrect recurrence

Interview Tip

Always explain:

Take one digit or take two digits

and count valid decoding possibilities.

Related Questions

  • House Robber
  • House Robber II
  • Coin Change
  • Climbing Stairs
  • Fibonacci

Final Takeaway

Decode Ways is one of the most important String Dynamic Programming problems.

It teaches:

  • DP on strings
  • decision making
  • state transitions
  • optimization techniques

Mastering Decode Ways prepares you for advanced string-based Dynamic Programming interview questions.