Word Break II

HARD✓ CHIP-TIMEDLC #140 — FULL STATEMENT ↗

The drill: A string and a dictionary of words — produce every way to insert spaces so the string reads as a sequence of dictionary words end to end, using each character exactly once.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A string and a dictionary of words arrive together. The task is to insert spaces into the string so it reads, left to right, as a sequence of dictionary words placed end to end with nothing left over.

Every character of the string must be consumed by exactly one dictionary word in the split — no character skipped, none reused across two words — and dictionary words can repeat as often as the split needs.

Every valid way to split the string counts as a separate sentence in the output; if no split at all works, the honest answer is an empty list rather than a partial attempt.

EX 01

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

→ ["a"]

MINIMUM SIZE, ONE WORD COVERS IT ALL

EX 02

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

→ ["a b"]

ONLY ONE VALID SPLIT

EX 03

s = "leetcode" · wordDict = ["leet", "code"]

→ ["leet code"]

A SINGLE UNAMBIGUOUS SPLIT

the string is short, generally well under twenty characters
dictionary words can repeat any number of times across one split
every character of the string is used by exactly one word in a valid split
all valid splits are returned; a string with none returns an empty list

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

The same suffix of the string gets revisited from wildly different starting splits. Before optimizing anything, notice that the work only depends on where a suffix begins, not on how you got there.

HINT 2 THE STRUCTURE

Recurse forward: at each position, try every dictionary word that matches the string starting there, and combine it with every sentence the rest of the string can form. What's the base case for an empty remainder?

HINT 3 ONE STEP FROM THE ANSWER

Cache the finished list of sentences for each starting index the first time it's computed — every other path that lands on that same index reads the cached list instead of re-splitting the same suffix from scratch.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE CACHED SUFFIXPATTERN · MEMOIZED RECURSIONs = "aaa" · wordDict = [a, aa, aaa]

STEP 1

s = 'aaa'. Each node is helper(i) — every way to split the suffix that starts at index i. helper(3) is the empty tail.

STEP 1 / 10 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/word-break-ii.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        words = set(wordDict)
        n = len(s)
        memo: Dict[int, List[str]] = {}

        def helper(start: int) -> List[str]:
            if start in memo:
                return memo[start]
            if start == n:
                return [""]
            sentences = []
            for end in range(start + 1, n + 1):
                piece = s[start:end]
                if piece in words:
                    for rest in helper(end):
                        sentences.append(piece if not rest else piece + " " + rest)
            memo[start] = sentences
            return sentences

        return helper(0)

TIME O(N² + TOTAL OUTPUT LENGTH)SPACE O(N² + TOTAL OUTPUT LENGTH)PYTHON · RACE PACE · 21 LN

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        words = set(wordDict)
        n = len(s)

        def helper(start: int) -> List[str]:
            if start == n:
                return [""]
            sentences = []
            for end in range(start + 1, n + 1):
                piece = s[start:end]
                if piece in words:
                    for rest in helper(end):
                        sentences.append(piece if not rest else piece + " " + rest)
            return sentences

        return helper(0)

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

class Solution {
    private Set<String> words;
    private String s;
    private Map<Integer, List<String>> memo;

    public List<String> wordBreak(String s, String[] wordDict) {
        this.s = s;
        this.words = new HashSet<>(Arrays.asList(wordDict));
        this.memo = new HashMap<>();
        return helper(0);
    }

    private List<String> helper(int start) {
        if (memo.containsKey(start)) {
            return memo.get(start);
        }
        List<String> sentences = new ArrayList<>();
        if (start == s.length()) {
            sentences.add("");
            memo.put(start, sentences);
            return sentences;
        }
        for (int end = start + 1; end <= s.length(); end++) {
            String piece = s.substring(start, end);
            if (words.contains(piece)) {
                for (String rest : helper(end)) {
                    sentences.add(rest.isEmpty() ? piece : piece + " " + rest);
                }
            }
        }
        memo.put(start, sentences);
        return sentences;
    }
}

TIME O(N² + TOTAL OUTPUT LENGTH)SPACE O(N² + TOTAL OUTPUT LENGTH)JAVA · RACE PACE · 34 LN

class Solution {
    private Set<String> words;
    private String s;

    public List<String> wordBreak(String s, String[] wordDict) {
        this.s = s;
        this.words = new HashSet<>(Arrays.asList(wordDict));
        return helper(0);
    }

    private List<String> helper(int start) {
        List<String> sentences = new ArrayList<>();
        if (start == s.length()) {
            sentences.add("");
            return sentences;
        }
        for (int end = start + 1; end <= s.length(); end++) {
            String piece = s.substring(start, end);
            if (words.contains(piece)) {
                for (String rest : helper(end)) {
                    sentences.add(rest.isEmpty() ? piece : piece + " " + rest);
                }
            }
        }
        return sentences;
    }
}

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

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