Word Break

Difficulty: Medium

Problem

Given a string s and a dictionary of words wordDict, return true if s can be segmented into a sequence of one or more dictionary words — every character used, words in order, and the same word reusable as many times as you like. "leetcode" with ["leet","code"] is a clean yes. The famous no: "catsandog" with ["cats","dog","sand","and","cat"] — it looks promising from both ends, yet every route strands the letters "og".

Example

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: "leetcode" splits as "leet" + "code" — every character covered, both pieces straight from the dictionary.

Brute-force approach

No separate brute-force phase — the exponential recursive splitter IS Step 1 of the guided walkthrough, where it gets diagnosed and upgraded into the memo and then the boolean table.

Optimal approach

Key insight: Every segmentation ends with some final word. dp[i] asks: is there ANY split point j where the front part is already breakable and the back part s[j:i] is a word? One yes is enough — that's OR.

Build a boolean table over prefixes: dp[i] = True when the first i characters split cleanly into dictionary words. Each prefix auditions every split point j as the start of its FINAL word — dp[j] True AND s[j:i] in the word set flips dp[i] True — and dp[n] answers for the whole string.

Steps

  1. Define the state: dp[i] = True if the first i characters can be split into dictionary words
  2. Seed dp[0] = True (the empty prefix) and pour wordDict into a hash set
  3. For each prefix end i from 1 to n, try every split point j < i
  4. Flip dp[i] True the moment dp[j] is True AND s[j:i] is in the set — then break, one witness suffices
  5. Return dp[n]: the verdict for the whole string

Time complexity: O(n² × average word check) · Space complexity: O(n) + dictionary set