Word Break
Determine whether a string can be split into one or more dictionary words. A word may be reused.
Work through the cases
3 examplesInput notation
The string on line 1; space-separated lowercase dictionary words on line 2.Expected result
true or false.Case 1
Input
applepenapple apple pen
Expected output
true
Case 2
Input
catsandog cats dog sand and cat
Expected output
false
Case 3
Input
aaaa a aa
Expected output
true
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
Can s be segmented into dictionary words? |s| ≤ 300; backtracking repeats the same suffixes. f[i] means the prefix s[0..i) can be split: try a cut j where f[j] is true and s[j..i) is in the dictionary. A hash set makes the membership test expected O(1).
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> words = new HashSet<>(wordDict);
int n = s.length();
boolean[] f = new boolean[n + 1];
f[0] = true;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < i; ++j) {
if (f[j] && words.contains(s.substring(j, i))) {
f[i] = true;
break;
}
}
}
return f[n];
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.