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

Word break — can string be segmented into dictionary words?

Problem Intuition & Objective

Determine if a string can be split into a sequence of dictionary words.

Time ComplexityO(n²)
Optimal
Space ComplexityO(n + dict size)
Memory Bounds
Optimal Algorithmic Approach

Bottom-up DP with HashSet for O(n²) total.

Core Invariants & Edge Cases

  • dp[i] = true if s[0..i-1] can be segmented
  • dp[i] = any dp[j] && s[j..i-1] in dict, for j < i
  • Put words in a HashSet for O(1) lookup
Previous ProblemUnique paths in a gridNext Problem Decode ways — number of ways to decode a digit string

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.