Word break Problem

The problem, simply

You get a string with no spaces, like catsanddog, and a list of words, the dictionary. Can you put spaces into the string so that every piece is a word from the dictionary? A word may be used many times.

Give back true or false. Below, n is the length of the string, L is the length of the longest dictionary word, and D is the total size of the dictionary.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every first word. If the start of the string is a dictionary word, ask the same question about the rest.

1. If the string is empty, return true.
2. For every length i, take the first i letters.
3. If they are a word and the rest can be split, return true.
4. If no first word works, return false.

The same rest gets asked about again and again. Here is the tree of questions for aaab with the words a and aa. Each number is where the rest starts.

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

    private boolean canBreak(String s, Set<String> dict) {
        if (s.isEmpty()) return true;                      // nothing left to split
        for (int i = 1; i <= s.length(); i++) {
            if (dict.contains(s.substring(0, i))           // first piece is a word
                    && canBreak(s.substring(i), dict)) {   // and the rest works too
                return true;
            }
        }
        return false;
    }
}

How long it takes: in the worst case every way of cutting is tried, and there are 2^(n - 1) ways, so O(2^n). Extra room: the call stack, up to n deep, O(n) (plus the substrings).

Way 2: the clever way

Answer each starting spot only once, from left to right. dp[i] says whether the first i letters can be split. Spot i sits between letter i - 1 and letter i.

1. dp[0] = true, the near bank.
2. For each i from 1 to n, look back at spots j from i - L to i - 1.
3. If dp[j] is true and the letters from j to i form a word, set dp[i] = true and stop looking.
4. The answer is dp[n], the far bank.

Looking back at most L letters is enough, because no word is longer than L.

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[] dp = new boolean[n + 1];   // dp[i]: first i letters can be split
        dp[0] = true;                        // the near bank
        for (int i = 1; i <= n; i++) {
            for (int j = Math.max(0, i - longest); j < i; j++) {
                if (dp[j] && dict.contains(s.substring(j, i))) {  // stand at j, plank to i
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
}

How long it takes: n spots, up to L planks each, and each plank costs up to L to cut out and look up, so O(n * L^2). Without the longest limit it is O(n^3). Extra room: the dp array plus the word set, O(n + D).

Watch out for

• Off by one. dp has n + 1 boxes. dp[i] is about the first i letters, and the piece is s.substring(j, i).
• Searching the list instead of a set. List.contains checks every word, which adds a factor of D. Put the words in a HashSet.
• Forgetting dp[0] = true. Without it nothing can ever become true.
• Memoizing by substring instead of by index. Use the start index as the key; it is cheaper and clearer.

What interviewers ask next

• Return all the sentences (LeetCode 140). Do the same search with memo by start index, but store the list of sentences for each start. The output itself can be exponential.
• A huge dictionary? Put the words in a trie. From each true spot, walk the trie forward letter by letter, and stop as soon as no word continues. This avoids building substrings.
• Fewest words in a split? Store a number in dp instead of true or false: dp[i] = min(dp[j] + 1).
• Is it like coin change? Yes. The words are coins, the string is the amount, and the order of coins is fixed by the letters.

Remember this

Grown-up words: the spots you can stand on are a 1D DP table, the river crossing is a reachability question on the positions, the repeated rest of the string is overlapping subproblems, and the dictionary is a hash set.