Word Break
The briefingthe full drill, in my own words
The drill: A string and a dictionary of words — decide whether the string can be sliced into a sequence of dictionary words back to back, reusing words as needed.
A string arrives alongside a dictionary of words, and the job is to decide whether the string can be cut into consecutive pieces where every piece matches some word in the dictionary — cuts have to line up back to back with nothing left over and nothing overlapping.
Words in the dictionary can be reused as many times as needed, and the dictionary itself might contain words that never end up used at all. The pieces have to appear in the same order as the string, left to right, never rearranged.
The output is just yes or no — whether at least one valid way to slice the string exists. There is no need to report which slicing works, only whether one does.
- the string and dictionary both stay short enough for quadratic work
- dictionary words can repeat inside the answer as many times as needed
- matching is case-sensitive and exact, no partial words
- the answer is a single true/false, not the actual slicing
The hintstake only what you need
HINT 1 THE NUDGE
Trying every place to cut the string and recursing on the remainder re-explores the same suffix again and again whenever two different cuts land at the same spot. What does that suffix's answer only depend on?
HINT 2 THE STRUCTURE
Whether the string can be broken starting at position i depends only on i and the dictionary — nothing about how you got to i matters. That's one boolean per position, not one per path.
HINT 3 ONE STEP FROM THE ANSWER
Build reachable[i] = true if some earlier reachable[j] is true and the slice between j and i is a dictionary word, starting from reachable[0] = true. The string breaks if reachable[n] is true.
Coach's boardthe pattern, step by step
Position 0, the empty prefix, is trivially reachable — nothing has been consumed yet.
The splitstwo paces, two languages
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
words = set(wordDict)
n = len(s)
reachable = [False] * (n + 1)
reachable[0] = True
for i in range(1, n + 1):
for j in range(i):
if reachable[j] and s[j:i] in words:
reachable[i] = True
break
return reachable[n]class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
words = set(wordDict)
n = len(s)
def canBreak(i: int) -> bool:
if i == n:
return True
for j in range(i + 1, n + 1): # try every possible next cut
if s[i:j] in words and canBreak(j):
return True
return False
return canBreak(0)class Solution {
public boolean wordBreak(String s, String[] wordDict) {
Set<String> words = new HashSet<>(Arrays.asList(wordDict));
int n = s.length();
boolean[] reachable = new boolean[n + 1];
reachable[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (reachable[j] && words.contains(s.substring(j, i))) {
reachable[i] = true;
break;
}
}
}
return reachable[n];
}
}class Solution {
public boolean wordBreak(String s, String[] wordDict) {
Set<String> words = new HashSet<>(Arrays.asList(wordDict));
return canBreak(s, 0, words);
}
private boolean canBreak(String s, int i, Set<String> words) {
int n = s.length();
if (i == n) {
return true;
}
for (int j = i + 1; j <= n; j++) { // try every possible next cut
if (words.contains(s.substring(i, j)) && canBreak(s, j, words)) {
return true;
}
}
return false;
}
}✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED