beingsde
Sign In
Back to all DSA patterns
Dynamic Programming•Pattern: DP•Medium

Decode ways — number of ways to decode a digit string

Problem Intuition & Objective

Count the number of ways to decode a numeric string into letters (A=1 … Z=26).

Time ComplexityO(n)
Optimal
Space ComplexityO(1) with two variables
Memory Bounds
Optimal Algorithmic Approach

1D DP — Fibonacci-style with validity checks.

Core Invariants & Edge Cases

  • dp[i] = ways to decode s[0..i-1]
  • Single digit valid (1-9): dp[i] += dp[i-1]
  • Two digits valid (10-26): dp[i] += dp[i-2]
Previous ProblemWord break — can string be segmented into dictionary words?Next Problem Jump game — can you reach the last index?

System Design & Architecture Roadmap

Coding interviews are only 50% of the bar. Master High-Level Design, distributed systems, and Object-Oriented LLD.

60+ HLD QuestionsSharding, caching, and real-time distributed systems.27 LLD BlueprintsObject-oriented design patterns with class diagrams.SDE Quick ReferenceLatency numbers and database selection matrix.