Word Break Problem

The problem, simply

You get a string s with all the spaces removed, like catsanddog, and a dictionary of words. Can you put spaces back so that every piece is a dictionary word? Words may be used more than once. Answer yes or no.

A story to remember it

Picture it

Examples

Way 1: the simple way

f(i) asks: can the text from position i to the end be split into words?

1. If i is the end of the string, yes.
2. Try every end j. If s[i..j) is a word and f(j) is yes, then yes.
3. If nothing works, no.

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

    private boolean canSplit(String s, Set<String> dict, int i) {
        if (i == s.length()) return true;               // nothing left to read
        for (int j = i + 1; j <= s.length(); j++) {
            if (dict.contains(s.substring(i, j)) && canSplit(s, dict, j)) {
                return true;                            // a word, and the rest works
            }
        }
        return false;
    }
}

How long it takes: a string of n letters can be cut in 2^(n-1) ways, and on a bad input like aaaaaaab the helper tries them all, O(2^n). Extra room: the call chain, O(n).

Way 2: the clever way

There are only n + 1 spots. Fill a row ok[0..n] where ok[i] says whether the first i letters can be split.

1. ok[0] = true (nothing to split).
2. For each spot i from 1 to n, look at every start j < i. If ok[j] is true and s[j..i) is in the dictionary, set ok[i] = true and stop looking.
3. Return ok[n].

Words can only be as long as the longest dictionary word L, so j only needs to go back L letters.

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> dict = new HashSet<>(wordDict);
        int longest = 0;
        for (String w : wordDict) longest = Math.max(longest, w.length());

        int n = s.length();
        boolean[] ok = new boolean[n + 1];
        ok[0] = true;                                    // empty start is fine
        for (int i = 1; i <= n; i++) {
            for (int j = Math.max(0, i - longest); j < i; j++) {
                if (ok[j] && dict.contains(s.substring(j, i))) {
                    ok[i] = true;                        // a word ends here after a tick
                    break;
                }
            }
        }
        return ok[n];
    }
}

How long it takes: n spots, each looking back at most L starts, and each lookup builds a piece of up to L letters, so O(n * L^2). Without the L limit it is O(n^3) in Java because of substring. Extra room: the row and the dictionary set, O(n + D) where D is the dictionary size.

Watch out for

• ok[0] must be true, or nothing can ever become true.
• substring(j, i) takes the end as exclusive. s[j..i) is exactly the letters j to i - 1.
• Put the dictionary in a HashSet. Searching a list for every piece is much slower.
• An empty string is true: it is zero words.

What interviewers ask next

• Return all the sentences, not yes or no (Word Break II). Use recursion with a memo that maps a start to the list of sentences for the rest. The output itself can be exponential.
• Very big dictionary with long words? Put the words in a trie. From each ticked spot, walk the trie forward letter by letter and tick every spot where a word ends. That avoids building substrings.
• Can you do it with BFS? Yes. Spots are nodes, a dictionary word from j to i is an edge. Ask whether spot n is reachable from spot 0.
• Fewest words in a split? Store the smallest word count instead of true or false.

Remember this

Grown-up words: the ticks are a boolean DP array, the spots are prefix lengths, a dictionary word between two spots is an edge in a graph, the memo version is top down DP, and the fast word lookup for long dictionaries is a trie.