#139 Word Break
the problem
In plain words
Can the string s be split into a sequence of one or more dictionary words? Words may be reused.
in s = "leetcode", wordDict = ["leet","code"]
out true
in s = "applepenapple", wordDict = ["apple","pen"]
out true
in s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
out false
- 1 ≤ s.length ≤ 300
- 1 ≤ wordDict.length ≤ 1000
- 1 ≤ wordDict[i].length ≤ 20
- All words are unique
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
pattern1D DP
A prefix is breakable if some shorter breakable prefix is followed by exactly one dictionary word. dp[i] = OR over j of (dp[j] && s[j..i) is a word).
solutions
From brute force to optimal
Try every dictionary prefix, recurse on the rest.
- start = n → true.
- For end in start+1..n: word and canBreak(end) → true.
Each of the n − 1 gaps can be a cut or not; "aaaa…ab" explores them all.
Recursion depth.
class Solution { public boolean wordBreak(String s, List<String> wordDict) { return canBreak(s, 0, new HashSet<>(wordDict)); } /** Can s[start..] be split into dictionary words? */ private boolean canBreak(String s, int start, Set<String> words) { if (start == s.length()) return true; for (int end = start + 1; end <= s.length(); end++) { if (words.contains(s.substring(start, end)) && canBreak(s, end, words)) return true; } return false; }}canBreak(start) only depends on start — cache it.
- Boolean[] memo, null = unknown.
n starts × n ends × O(n) substring + hash.
Memo + stack (plus the word set).
class Solution { public boolean wordBreak(String s, List<String> wordDict) { return canBreak(s, 0, new HashSet<>(wordDict), new Boolean[s.length()]); } private boolean canBreak(String s, int start, Set<String> words, Boolean[] memo) { if (start == s.length()) return true; if (memo[start] != null) return memo[start]; for (int end = start + 1; end <= s.length(); end++) { if (words.contains(s.substring(start, end)) && canBreak(s, end, words, memo)) { return memo[start] = true; } } return memo[start] = false; }}dp[i] = can the first i characters be split?
- dp[0] = true.
- For each i, for each j < i: dp[j] && set.contains(s.substring(j, i)) → dp[i] = true.
- Return dp[n].
n² (j, i) pairs, each substring + hash costs O(n). Limit j to i − maxWordLen for O(n·L²).
The dp array (plus the word set).
class Solution { public boolean wordBreak(String s, List<String> wordDict) { Set<String> words = new HashSet<>(wordDict); // O(1) average lookups int n = s.length(); boolean[] dp = new boolean[n + 1]; // dp[i]: can the first i chars be split? dp[0] = true; // the empty prefix is trivially fine for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (dp[j] && words.contains(s.substring(j, i))) { // good prefix + one word dp[i] = true; break; } } } return dp[n]; }}Mark breakable prefixes
in the room
How to say it in the interview
talk track
- Convert the list to a HashSet first —
List.containsis O(size). - Mention the max-word-length optimisation (words ≤ 20 chars): only check j ≥ i − 20.
traps
- Greedy longest-match fails: "cars" with {"car", "ca", "rs"} needs "ca" + "rs".
- dp array of size n, not n + 1 — then the empty prefix has nowhere to live.
what they ask next
Follow-ups
Return all sentences (LC 140)?
Backtracking with memo of start → list of sentences. Output can be exponential.
before you submit
Edge cases to test
- Words can be reused: "applepenapple" → true.
- Greedy longest match fails: "cars" with [car, ca, rs] → true via ca + rs.
- "aaaa…ab" with only a-words → false; plain recursion explores about 2ⁿ splits here.
practise next
Similar problems
- #91Decode WaysMediumin Dynamic Programming
- #131Palindrome PartitioningMediumin Backtracking
- #208Implement Trie (Prefix Tree)Mediumin Tries