Word Break

MEDIUM✓ CHIP-TIMEDLC #139 — FULL STATEMENT ↗

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.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

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.

EX 01

s = "a" · wordDict = ["a"]

→ true

MINIMUM SIZE, EXACT MATCH

EX 02

s = "a" · wordDict = ["b"]

→ false

MINIMUM SIZE, NO MATCH AT ALL

EX 03

s = "code" · wordDict = ["co", "de"]

→ true

TWO PIECES, BOTH NEEDED

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 HINTS — TAKE 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 BOARD — THE PATTERN, STEP BY STEP

REACHABLE PREFIXESPATTERN · REACHABLE PREFIXESs = "applepie" · wordDict = ["apple", "pie"]

REACHABLE POSITIONS

reachable(0) → true

STEP 1

Position 0, the empty prefix, is trivially reachable — nothing has been consumed yet.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/word-break.py — RACE PACE

LANG ▸

PACE ▸

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]

TIME O(N^2)SPACE O(N)PYTHON · RACE PACE · 12 LN

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)

TIME O(2^N)SPACE O(N)PYTHON · TRAINING PACE · 14 LN

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];
    }
}

TIME O(N^2)SPACE O(N)JAVA · RACE PACE · 17 LN

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;
    }
}

TIME O(2^N)SPACE O(N)JAVA · TRAINING PACE · 19 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED