‹ DS&A interview · Socratic
DSA · Dynamic Programming · #185

Word Break

Module 47 · difficulty 3/5·⏱ 30:00starts on first keystroke

Given a string `s` and a list of strings `wordDict` (the dictionary), implement `wordBreak(s, wordDict)` that returns `true` if `s` can be segmented into a space-separated sequence of one or more dictionary words, and `false` otherwise. The same dictionary word may be reused any number of times in the segmentation. Dictionary words are all distinct.

Examples
  • s = "leetcode", wordDict = ["leet","code"] → true — "leetcode" = "leet" + "code".
  • s = "applepenapple", wordDict = ["apple","pen"] → true — "apple" is reused: "apple" + "pen" + "apple".
  • s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] → false — No segmentation consumes the whole string.
Constraints
  • · 1 <= s.length <= 300
  • · 1 <= wordDict.length <= 1000
  • · 1 <= wordDict[i].length <= 20
  • · s and wordDict[i] consist of only lowercase English letters.
  • · All the strings of wordDict are unique.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.