Word Break Problem using Backtracking

The problem, simply

You get a string with no spaces, like catsanddog, and a dictionary of words. Add spaces so that every piece is a dictionary word. A word may be used more than once.

Give back every sentence you can make. If there is none, give back an empty list.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every word the text starts with. For each one, cut it off and solve the rest the same way. When the rest is empty, the words you cut form a sentence.

1. If start is at the end, join the current words with spaces and save the sentence.
2. For each end after start, if s[start..end) is in the dictionary, add it, solve from end, then remove it.

import java.util.*;

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

    private void cut(String s, int start, Set<String> dict, List<String> words, List<String> result) {
        if (start == s.length()) {
            result.add(String.join(" ", words));    // every letter is used: a sentence
            return;
        }
        for (int end = start + 1; end <= s.length(); end++) {
            String word = s.substring(start, end);
            if (dict.contains(word)) {
                words.add(word);
                cut(s, end, dict, words, result);
                words.remove(words.size() - 1);     // undo and try a longer word
            }
        }
    }
}

How long it takes: there are 2^(n-1) ways to put spaces into n letters, and each costs up to O(n) to build. On the slow trap above it tries a huge number of cuts and finds nothing. O(n * 2^n). Extra room: the words list and the call stack, O(n), besides the answers.

Way 2: the clever way

The search keeps asking the same question: "what sentences can the text from letter i on make?" The answer depends only on i. So write each answer in a notebook the first time, and read it from the notebook every later time.

1. If the notebook has letter start, return what it says.
2. If start is the end, the answer is one empty sentence.
3. For each word that the text starts with at start, get the sentences for the rest, and put the word in front of each one.
4. Write the list in the notebook for start and return it.

import java.util.*;

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        return solve(s, 0, new HashSet<>(wordDict), new HashMap<>());
    }

    private List<String> solve(String s, int start, Set<String> dict, Map<Integer, List<String>> memo) {
        if (memo.containsKey(start)) return memo.get(start);   // already worked out
        List<String> out = new ArrayList<>();
        if (start == s.length()) {
            out.add("");                                       // one empty sentence
            return out;
        }
        for (int end = start + 1; end <= s.length(); end++) {
            String word = s.substring(start, end);
            if (!dict.contains(word)) continue;
            for (String rest : solve(s, end, dict, memo)) {
                out.add(rest.isEmpty() ? word : word + " " + rest);
            }
        }
        memo.put(start, out);                                  // write it in the notebook
        return out;
    }
}

How long it takes: each of the n starting letters is solved once, and each one tries up to n words, so O(n^2) look-ups, plus the time to build the output, S letters in total. The slow trap now takes O(n^2) and returns quickly. Extra room: the notebook holds every partial sentence, O(n + S).

The output itself can be exponential (think aaaa... with words a and aa), and no method can beat writing it down. The notebook only removes repeated work.

Watch out for

• Checking the dictionary as a List. contains on a list is slow. Turn it into a HashSet first.
• Forgetting the space rule. Do not add a space before the empty rest, or sentences end with a trailing space.
• Trying word lengths longer than the longest dictionary word. Limit end to start + maxLen to save time.

What interviewers ask next

• Only answer yes or no (Word Break I). Use a table: ok[i] is true if some word ends at i and ok was true where that word starts. That is O(n^2), or O(n * maxLen).
• Count the sentences instead of listing them. Store counts in the notebook instead of lists.
• The dictionary is huge. Put it in a trie. Then from each start walk the trie letter by letter, and stop as soon as no word continues.
• Should you check first if any sentence exists? Yes, a quick yes or no table first avoids building lists on inputs with no answer.

Remember this

Grown-up words: the cutting is backtracking, the notebook is memoization (top down dynamic programming), the same question asked many times is overlapping subproblems, and a fast word list is a hash set or a trie.