Word Break
Solve this Problems and a dictionary of words wordDict, determine whether s can be broken into consecutive dictionary words with no leftover characters — the same word can be reused as many times as the split calls for.
The naive way tries every possible split point recursively, but the same starting position gets re-explored again and again through different earlier splits — that's what makes it exponential. Tracking, for every position, whether the prefix up to there is reachable at all (a simple boolean array) turns that repeated work into a single pass: once a position is known reachable, walking forward through a trie of the dictionary finds every word that starts there in one sweep, marking each landing spot reachable too.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ s.length ≤ 300 - ◆
1 ≤ wordDict.length ≤ 1000 - ◆
1 ≤ wordDict[i].length ≤ 20 - ◆
s and wordDict[i] consist of lowercase English letters - ◆
all strings in wordDict are unique
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Recursive Backtracking
BruteStarting from position 0, try every possible next word: for each candidate end point, check whether that substring is in the dictionary, and if so, recurse from there. Succeed the moment any recursive path reaches the end of the string. With no memoization, overlapping subproblems (the same starting position reached through different earlier splits) get re-explored from scratch every time, which blows up exponentially on inputs like a long run of the same character.
O(2ⁿ)O(n)1class Solution {
2 public boolean wordBreak(String s, String[] wordDict) {
3 return canBreak(s, 0, new HashSet<>(Arrays.asList(wordDict)));
4 }
5
6 private boolean canBreak(String s, int start, Set<String> dict) {
7 if (start == s.length()) return true;
8 for (int end = start + 1; end <= s.length(); end++) {
9 if (dict.contains(s.substring(start, end)) && canBreak(s, end, dict)) {
10 return true;
11 }
12 }
13 return false;
14 }
15}Optimal — Bottom-Up DP with a Trie
OptimalInsert the whole dictionary into a trie up front. Then build a boolean array dp where dp[i] means "the first i characters of s can be fully segmented." dp[0] starts true (an empty prefix trivially breaks). For every position i where dp[i] is already true, walk forward through the trie one character at a time — every time that walk passes a node marking the end of a dictionary word, the position just after it becomes reachable too. No substring ever gets re-examined from two different starting points, so each position's work is bounded by L, the longest dictionary word.
O(n · L)O(n + N)1class Solution {
2 static class TrieNode {
3 TrieNode[] children = new TrieNode[26];
4 boolean isEnd = false;
5 }
6
7 public boolean wordBreak(String s, String[] wordDict) {
8 TrieNode root = new TrieNode();
9 for (String word : wordDict) {
10 TrieNode node = root;
11 for (char c : word.toCharArray()) {
12 int idx = c - 'a';
13 if (node.children[idx] == null) {
14 node.children[idx] = new TrieNode();
15 }
16 node = node.children[idx];
17 }
18 node.isEnd = true;
19 }
20
21 int n = s.length();
22 boolean[] dp = new boolean[n + 1];
23 dp[0] = true;
24 for (int i = 0; i < n; i++) {
25 if (!dp[i]) continue;
26 TrieNode node = root;
27 for (int j = i; j < n; j++) {
28 int idx = s.charAt(j) - 'a';
29 if (node.children[idx] == null) break;
30 node = node.children[idx];
31 if (node.isEnd) {
32 dp[j + 1] = true;
33 }
34 }
35 }
36 return dp[n];
37 }
38}