Word Break II

Hard Recursion & Backtracking Choice per Position Original on LeetCode

Word Break II is a hard recursion & backtracking problem solved with the choice per position pattern. The best approach, optimal (memoized dfs on suffixes), runs in O(n² + S · n) time and O(S · n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (backtracking) up.

Problem

You are given a string s and a list of distinct words wordDict. Insert spaces into s so that every piece is a word from the dictionary, and return all sentences you can build this way.

The same dictionary word may be used any number of times. Return the sentences in any order; if there is no way to split s, return an empty list.

Examples

Example 1

Input
s = "sunflowerbed", wordDict = ["sun", "flower", "sunflower", "bed", "flowerbed"]
Output
["sun flower bed", "sun flowerbed", "sunflower bed"]
Why
Three different ways split the string into dictionary words; the order of the sentences does not matter.

Example 2

Input
s = "redcar", wordDict = ["red", "re", "dca", "car"]
Output
["red car"]
Why
"re dca r" fails because "r" alone is not a word, so only one sentence works.

Example 3

Input
s = "bluesky", wordDict = ["blue", "sk", "skies"]
Output
[]
Why
After "blue", the rest "sky" cannot be built from the dictionary.

Constraints

  • 1 <= s.length <= 20
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 10
  • s and every word consist only of lowercase English letters
  • All words in wordDict are distinct
  • The total number of sentences in the answer does not exceed 10^5

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (backtracking)O(2^n · n)O(n)
Optimal (memoized DFS on suffixes)O(n² + S · n)O(S · n)

1Brute force (backtracking)

TimeO(2^n · n)In the worst case every one of the n - 1 gaps can be a split point, and each sentence costs O(n) to build; dead ends are explored again every time.
SpaceO(n)Recursion depth and the current path are at most n (output not counted).

Build sentences left to right. At position start, try every end index; if s[start..end) is a dictionary word, append it to the current path and recurse from end. When start reaches the end of the string, join the path into a sentence.

  1. Put the dictionary into a hash set.
  2. dfs(start, path): if start == n, add the joined path to the result.
  3. For end from start + 1 to n: if s[start..end) is in the set, push it, call dfs(end, path), pop it.
  4. Call dfs(0, []) and return the result.
class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        Set<String> dict = new HashSet<>(wordDict);
        List<String> result = new ArrayList<>();
        dfs(s, 0, dict, new ArrayList<>(), result);
        return result;
    }

    private void dfs(String s, int start, Set<String> dict, List<String> path, List<String> result) {
        if (start == s.length()) {
            result.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);
                dfs(s, end, dict, path, result);
                path.remove(path.size() - 1);
            }
        }
    }
}

2Optimal (memoized DFS on suffixes)

TimeO(n² + S · n)Each of the n suffixes tries n end positions once; S is the number of partial sentences built in total, each costing O(n) characters to concatenate.
SpaceO(S · n)The memo stores every partial sentence for every suffix.

Let solve(start) return every sentence that splits the suffix s[start..]. It depends only on start, so compute it once and cache it. For each dictionary word that is a prefix of the suffix, prepend the word to each sentence of solve(end). A suffix with no valid split is cached as an empty list, so dead ends are never explored twice.

  1. Put the dictionary into a hash set and create a memo map from start index to list of sentences.
  2. solve(n) = [""] (one empty sentence).
  3. solve(start): for each end in start+1..n with s[start..end) in the set, for each tail in solve(end), add word if tail is empty else word + ' ' + tail.
  4. Store the list in the memo and return it; the answer is solve(0).
class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        Set<String> dict = new HashSet<>(wordDict);
        Map<Integer, List<String>> memo = new HashMap<>();
        return solve(s, 0, dict, memo);
    }

    private List<String> solve(String s, int start, Set<String> dict, Map<Integer, List<String>> memo) {
        if (memo.containsKey(start)) return memo.get(start);
        List<String> out = new ArrayList<>();
        if (start == s.length()) {
            out.add("");
        } else {
            for (int end = start + 1; end <= s.length(); end++) {
                String word = s.substring(start, end);
                if (!dict.contains(word)) continue;
                for (String tail : solve(s, end, dict, memo)) {
                    out.add(tail.isEmpty() ? word : word + " " + tail);
                }
            }
        }
        memo.put(start, out);
        return out;
    }
}

Edge cases to test

  • No valid split at all: return an empty list
  • The whole string is a single dictionary word
  • A dictionary word can be reused many times, like s = "aaaa" with ["a", "aa"]
  • Many dead-end prefixes that fail only at the last character

Hints

Hint 1

Try every dictionary word that is a prefix of the remaining string, then recurse on what is left.

Hint 2

The same suffix of s is reached through many different prefixes. Its list of sentences never changes.

Hint 3

Memoize: for each start index, store the list of sentences that split s[start..].

FAQ

What is the best time complexity for Word Break II?

Optimal (memoized DFS on suffixes) runs in O(n² + S · n) time and O(S · n) extra space. Each of the n suffixes tries n end positions once; S is the number of partial sentences built in total, each costing O(n) characters to concatenate.

Which pattern does Word Break II use?

It is a recursion & backtracking problem that uses the choice per position pattern. Other problems with the same pattern: Letter Combinations of a Phone Number, Confusing Number II, Strobogrammatic Number II.

Is there a brute force solution for Word Break II?

Yes. Brute force (backtracking) takes O(2^n · n) time and O(n) space. Build sentences left to right.

Which edge cases should I test for Word Break II?

No valid split at all: return an empty list; The whole string is a single dictionary word; A dictionary word can be reused many times, like s = "aaaa" with ["a", "aa"]; Many dead-end prefixes that fail only at the last character.