Word Break II

NeetCode: Word Break II · LeetCode: 140. Word Break II · Difficulty: Hard

Given a string s and a dictionary of words, add spaces to s to build every sentence in which each word is in the dictionary. Words may be reused. Return all sentences in any order (the programs below print them sorted).

Example

Text

Input:  s = "catsanddog", wordDict = [cat, cats, and, sand, dog]
Output: ["cat sand dog", "cats and dog"]

Input:  s = "pineapplepenapple", wordDict = [apple, pen, applepen, pine, pineapple]
Output: ["pine apple pen apple", "pine applepen apple", "pineapple pen apple"]

Input:  s = "catsandog", wordDict = [cats, dog, sand, and, cat]
Output: []

Brute force: plain backtracking

At position start, try every end end > start such that s.substring(start, end) is a dictionary word, add it to the current path, and recurse from end. When start reaches the end of the string, join the path into a sentence with String.join(" ", path). This finds all answers but explores dead ends repeatedly: if the tail of the string can never be split, every prefix arrangement that reaches that tail rediscovers the failure.

LeetCode's Java signature is List<String> wordBreak(String s, List<String> wordDict). The dictionary becomes a HashSet<String> so a word lookup is O(L) for a word of length L (hashing reads the characters). The method returns sentences in discovery order, and main sorts them before printing.

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Main {
    static class Solution {
        public List<String> wordBreak(String s, List<String> wordDict) {
            Set<String> dict = new HashSet<>(wordDict);
            List<String> out = new ArrayList<>();
            backtrack(s, 0, dict, new ArrayList<>(), out);
            return out;
        }

        private void backtrack(String s, int start, Set<String> dict, List<String> path, List<String> out) {
            if (start == s.length()) {
                out.add(String.join(" ", path));
                return;
            }
            for (int end = start + 1; end <= s.length(); end++) {
                String word = s.substring(start, end);
                if (dict.contains(word)) {
                    path.add(word);
                    backtrack(s, end, dict, path, out);
                    path.remove(path.size() - 1);
                }
            }
        }
    }

    static List<String> sorted(List<String> list) {
        List<String> copy = new ArrayList<>(list);
        Collections.sort(copy);
        return copy;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(sorted(s.wordBreak("catsanddog", List.of("cat", "cats", "and", "sand", "dog"))));
        System.out.println(sorted(s.wordBreak("pineapplepenapple", List.of("apple", "pen", "applepen", "pine", "pineapple"))));
        System.out.println(sorted(s.wordBreak("catsandog", List.of("cats", "dog", "sand", "and", "cat"))));
    }
}

Output

[cat sand dog, cats and dog]
[pine apple pen apple, pine applepen apple, pineapple pen apple]
[]

For a string like aaaa...ab with dictionary [a, aa, aaa, ...] the number of ways to split the a-prefix is exponential and every one of them fails on the final b. Time: exponential, O(2^n) paths in the worst case, times O(n) per sentence built. Space: O(n) recursion plus the output.

Optimal: memoised backtracking

The set of sentences for the suffix s[start..] depends only on start, so memo caches every sentence for that suffix, keyed by start in a HashMap<Integer, List<String>>. To compute it, take each dictionary word s.substring(start, end) and prepend it to every sentence of the suffix at end (a bare word if end is the end of the string). A suffix that cannot be split stores an empty list, so that failure is computed only once.

The cached list is returned by reference. The callers only read it, so no copy is needed.

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Main {
    static class Solution {
        public List<String> wordBreak(String s, List<String> wordDict) {
            Set<String> dict = new HashSet<>(wordDict);
            return sentences(s, 0, dict, new HashMap<>());
        }

        private List<String> sentences(String s, int start, Set<String> dict, Map<Integer, List<String>> memo) {
            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;
                }
                if (end == s.length()) {
                    result.add(word);
                } else {
                    for (String rest : sentences(s, end, dict, memo)) {
                        result.add(word + " " + rest);
                    }
                }
            }
            memo.put(start, result);
            return result;
        }
    }

    static List<String> sorted(List<String> list) {
        List<String> copy = new ArrayList<>(list);
        Collections.sort(copy);
        return copy;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(sorted(s.wordBreak("catsanddog", List.of("cat", "cats", "and", "sand", "dog"))));
        System.out.println(sorted(s.wordBreak("pineapplepenapple", List.of("apple", "pen", "applepen", "pine", "pineapple"))));
        System.out.println(sorted(s.wordBreak("catsandog", List.of("cats", "dog", "sand", "and", "cat"))));
    }
}

Output

[cat sand dog, cats and dog]
[pine apple pen apple, pine applepen apple, pineapple pen apple]
[]

Memoisation removes the repeated failed work, so dead ends cost only O(n) states. The output itself can be exponentially large (for aaaa... with [a, aa] there are Fibonacci-many sentences), so the output size is a lower bound. Time: O(n^2) substring checks for the states plus the total size of all sentences built. Space: the memo stores the sentences of every suffix, so it is proportional to that total size (O(n) states, each holding its list).

How to explain it in an interview

Baseline: at each start index try every prefix that is a dictionary word and recurse. The same unsplittable tails are solved again and again, so the running time is exponential.
Key insight: the sentences for the suffix s[start..] depend only on start, so cache them in a HashMap<Integer, List<String>>; a dead suffix caches an empty list.
Steps: (1) put the words in a HashSet; (2) sentences(start) checks the memo first; (3) for each end, if s.substring(start, end) is a word: either it is the last word (add it) or prepend it to every sentence of sentences(end); (4) store and return the list.
Complexity: O(n²) substring checks for the states plus the total size of the output, which can itself be exponential (aaaa... with [a, aa]).
Follow-ups and pitfalls: deciding only whether a split exists is Word Break I, a boolean DP. Store an empty list for a dead suffix, not null, so the memo lookup cannot confuse "not computed" with "no sentences". A caller that modifies the returned list would also change the memo, so the code only reads it.