Topics › Recursion and Backtracking › Trying out all Combos / Hard

Word Break (print all ways)

Medium TUF ID 2757 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given a string s and a dictionary wordDict of distinct, non-empty words. Insert spaces into s so that every resulting piece is a dictionary word, and return all sentences that can be formed this way, in any order. A word may be used any number of times. If no segmentation exists, return an empty list.

This is the “list every answer” version of Word Break: instead of asking whether s can be split, it asks for every split.

Constraints (LeetCode 140): 1 ≤ s.length ≤ 20, 1 ≤ wordDict.length ≤ 1000, 1 ≤ wordDict[i].length ≤ 10, lowercase English letters only, and the inputs are chosen so that the answer has at most 10^5 sentences.

Example 1

s = "catsanddog", wordDict = ["cat", "cats", "and", "sand", "dog"]
answer = ["cats and dog", "cat sand dog"]     // "cat" and "cats" both start s, and each leads to one sentence

Example 2

s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
answer = []                                   // every split leaves "og", which is not a word

A third case worth keeping in mind: s = "pineapplepenapple" with ["apple", "pen", "applepen", "pine", "pineapple"] has three answers: "pine apple pen apple", "pineapple pen apple" and "pine applepen apple". Words that are prefixes of other words are what make several answers possible.

Approach 1: Brute force, plain backtracking

Intuition. However a sentence looks, its first word is a dictionary word that matches s at position 0. Once that word is chosen, the rest of the sentence is a segmentation of the remaining suffix, which is the same problem on a shorter string. So try every dictionary word that matches at the current position, append it to a running list of words, recurse from just past it, and remove it again when the call returns. When the position reaches the end of s, the words in the list cover s exactly, so join them with spaces and record a sentence.

Unlike the yes/no version, we cannot stop at the first success: every branch that can finish must be explored. That part is unavoidable. What makes this version slow is the branches that cannot finish: they are explored in full and thrown away.

Algorithm.

1. backtrack(start): if start == s.length(), add String.join(" ", words) to the output and return.
2. For each dictionary word w that s contains at position start: append w to words, call backtrack(start + w.length()), then remove the last word.
3. Start with backtrack(0) and an empty list of words.

static List<String> bruteForce(String s, List<String> wordDict) {
    List<String> out = new ArrayList<>();
    backtrack(s, 0, wordDict, new ArrayList<>(), out);
    return out;
}

private static void backtrack(String s, int start, List<String> dict, List<String> words, List<String> out) {
    if (start == s.length()) {                           // the chosen words cover s exactly
        out.add(String.join(" ", words));
        return;
    }
    for (String w : dict) {
        if (w.isEmpty() || !s.startsWith(w, start)) continue;
        words.add(w);
        backtrack(s, start + w.length(), dict, words, out);
        words.remove(words.size() - 1);                  // undo the choice before trying the next word
    }
}

Complexity. Time O(2^n · k · L) in the worst case, where k is the dictionary size and L the longest word: there are up to 2^(n-1) ways to place cuts, and every node of the search tries all k words with an O(L) comparison. Space O(n) for the recursion and the word list, besides the output.

The bad case is not one with many answers; it is one with many dead ends. For s = "aaaaaaaaaaaaaaaaaaab" (19 as and a b) with ["a", "aa", "aaa", "aaaa"] the answer is empty, yet the backtracking enumerates about 147,000 ways to split the run of as, and every one of them fails at the b. It also rediscovers the same dead suffix from every prefix that reaches it.

Approach 2: Better, memoise the sentences of each suffix

Intuition. The sentences that can be formed from the suffix s[start, n) depend only on start, not on how we got there. So define sentencesFrom(start) as the full list of sentences for that suffix, and cache it. To compute it, try every end position: if s[start, end) is a word, prepend it to each sentence of sentencesFrom(end). Each suffix is solved once; a dead suffix is solved once too and cached as an empty list, so it can never be explored twice.

The base case needs care. The empty suffix has exactly one segmentation, the one with no words, so it returns [""], not []. Returning an empty list there would make every caller see “no sentences” and the answer would always be empty. When prepending, a word followed by the empty sentence is just the word, which avoids a trailing space.

Algorithm.

1. If start == n, return [""].
2. If memo has start, return the cached list.
3. For each end from start + 1 to n: if word = s[start, end) is in the dictionary set, for every rest in sentencesFrom(end) add word (when rest is empty) or word + " " + rest.
4. Cache and return the list.

static List<String> better(String s, List<String> wordDict) {
    return sentencesFrom(s, 0, new HashSet<>(wordDict), new HashMap<>());
}

private static List<String> sentencesFrom(String s, int start, Set<String> dict, Map<Integer, List<String>> memo) {
    if (start == s.length()) return List.of("");         // exactly one way to split nothing: use no words
    List<String> cached = memo.get(start);
    if (cached != null) return cached;
    List<String> result = new ArrayList<>();
    for (int end = start + 1; end <= s.length(); end++) {
        String word = s.substring(start, end);
        if (!dict.contains(word)) continue;
        for (String rest : sentencesFrom(s, end, dict, memo)) {
            result.add(rest.isEmpty() ? word : word + " " + rest);
        }
    }
    memo.put(start, result);
    return result;
}

Complexity. Let S be the number of sentences in the answer. Time O(n³ + n² · S): each of the n starts runs once and tries O(n) end positions, each hashing a substring of length O(n); every suffix list that gets computed belongs to a suffix reachable from a valid prefix, so it holds at most S sentences of length O(n). Space O(n² · S) in the worst case for the memo, which keeps the list of every suffix alive until the end, not just the final answer.

On the dead-end input above, this does only O(n²) substring checks and returns at once. The cost is memory: intermediate lists for every suffix are built and kept, and the same text gets copied again at every level as words are prepended.

Approach 3: Optimal, Word Break table plus pruned backtracking

Intuition. The brute force was slow only because of branches that cannot finish. The yes/no Word Break DP tells us exactly which suffixes can finish. Let canBreak[i] mean “the suffix s[i, n) can be split into words”. Then canBreak[n] = true, and for smaller i, canBreak[i] is true exactly when some word s[i, end) is followed by a breakable suffix, canBreak[end]. Filling it from right to left guarantees each canBreak[end] is final when it is read. Only words up to the longest dictionary length maxLen can match, which bounds the inner loop.

Now backtrack exactly as in Approach 1, but step to end only if s[start, end) is a word and canBreak[end] is true. Every call is then made on a suffix that is known to split, so every node of the search tree has at least one finished sentence below it. Nothing is explored and thrown away, and no intermediate lists are stored: one StringBuilder holds the sentence under construction and is trimmed back to its previous length on the way out.

Algorithm.

1. Put the words in a set and record maxLen.
2. Fill canBreak from i = n - 1 down to 0, stopping at the first word s[i, end) with canBreak[end] true.
3. If canBreak[0] is false, return an empty list.
4. collect(start): at start == n record the sentence. Otherwise, for each end within maxLen of start with canBreak[end] true and s[start, end) in the set: append a space (unless this is the first word) and the word, recurse, then cut the builder back to its old length.

static List<String> optimal(String s, List<String> wordDict) {
    Set<String> dict = new HashSet<>(wordDict);
    int maxLen = 0;
    for (String w : dict) maxLen = Math.max(maxLen, w.length());
    int n = s.length();
    boolean[] canBreak = new boolean[n + 1];             // canBreak[i]: the suffix s[i, n) splits into words
    canBreak[n] = true;
    for (int i = n - 1; i >= 0; i--) {
        for (int end = i + 1; end <= n && end - i <= maxLen; end++) {
            if (canBreak[end] && dict.contains(s.substring(i, end))) {
                canBreak[i] = true;
                break;
            }
        }
    }
    List<String> out = new ArrayList<>();
    if (canBreak[0]) collect(s, 0, dict, maxLen, canBreak, new StringBuilder(), out);
    return out;
}

private static void collect(String s, int start, Set<String> dict, int maxLen, boolean[] canBreak,
                            StringBuilder sentence, List<String> out) {
    if (start == s.length()) {
        out.add(sentence.toString());
        return;
    }
    int before = sentence.length();
    for (int end = start + 1; end <= s.length() && end - start <= maxLen; end++) {
        if (!canBreak[end] || !dict.contains(s.substring(start, end))) continue;   // dead suffix or not a word
        if (start > 0) sentence.append(' ');
        sentence.append(s, start, end);
        collect(s, end, dict, maxLen, canBreak, sentence, out);
        sentence.setLength(before);                      // undo: drop the word and its space
    }
}

Dry run on Example 1, s = "catsanddog", maxLen = 4. The table is filled right to left:

The search from 0 tries cat (end 3, true) and cats (end 4, true). From 3, only sand qualifies; from 4, only and; from 7, only dog. Both paths reach the end, so the output is "cat sand dog" and "cats and dog", and no call was ever made on a suffix that fails.

Complexity. Time O(n · L² + S · n · L²), where L = maxLen. The table costs n positions times at most L candidate words of length at most L. In the search tree every node has a sentence below it, so it has at most S leaves and depth at most n, hence at most n · S nodes, each trying at most L words. Space O(n) for the table, the recursion and the builder, besides the output.

Both Approach 2 and Approach 3 are output-sensitive, and nothing can beat O(total length of the output), since every sentence must be written. Approach 3 gets there with no memo lists and no repeated copying of suffix text, which is why it is the one to prefer.

Edge cases and pitfalls

• No segmentation. Return an empty list. Approach 3 sees canBreak[0] == false and returns before any search.
• Empty string. By the same logic as the base case, "" has one segmentation with zero words, so all three methods return [""]. LeetCode never asks it, but the convention must match between approaches.
• Words that are prefixes of other words. cat/cats, pine/pineapple, apple/applepen. Greedy longest or shortest match loses answers; every end position must be tried.
• Reusing a word. "aaaa" with ["a", "aa"] has five answers (a a a a, a a aa, a aa a, aa a a, aa aa). Nothing removes a word after use, which is correct.
• Spaces. Build sentences so there is never a leading or trailing space: the rest.isEmpty() check in Approach 2 and the start > 0 check in Approach 3 handle this.
• Exponential output. Twenty as with every word a, aa, …, aaaaaaaaaa gives hundreds of thousands of sentences. No algorithm can avoid writing them; this is why the problem caps the answer size.
• Duplicate dictionary entries. Approach 1 iterates over the list, so a word listed twice would emit every sentence using it twice. The set-based approaches are immune; for the brute force, convert to a set first if the input is not guaranteed distinct.
• Empty dictionary word. It would make the brute force recurse at the same position forever, so it is skipped explicitly; substring-based approaches never produce an empty piece.

Related problems

• Word Break is the yes/no version; its DP table is exactly the pruning table used in Approach 3.
• Palindrome partitioning lists every way to cut a string, with “is a palindrome” as the test for each piece instead of “is a word”.
• Combination Sum enumerates every multiset of reusable numbers, the same “pick, recurse, unpick” pattern with reuse allowed.
• Permutations of a String is another backtracking problem whose answer is a full list rather than a count.
• Longest Word with All Prefixes uses a trie for prefix lookups, an alternative to substring hashing when the dictionary is large.