Problem statement

Given a string s and a dictionary wordDict of distinct words, insert spaces into s to turn it into a sentence in which every word is in the dictionary. A dictionary word may be used any number of times.

Return all such sentences, sorted in ascending lexicographic order (by character code, so a space sorts before any letter). Return an empty list if there are none.

Example 1

Input: s = "codekairo", wordDict = ["code","kai","ro","kairo","co","de"]
Output: ["co de kai ro","co de kairo","code kai ro","code kairo"]

Example 2

Input: s = "aaaa", wordDict = ["a","aa"]
Output: ["a a a a","a a aa","a aa a","aa a a","aa aa"]

Example 3

Input: s = "duel", wordDict = ["du","e"]
Output: []
Explanation: Nothing in the dictionary ends with `l`.

Constraints

• 1 <= s.length <= 20
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 10
• s and wordDict[i] consist of only lowercase English letters
• All the strings of wordDict are unique
• The total length of the answer does not exceed 10^5

Hints for Word Break II

1. Hint 1

   Build sentences left to right: at position i, try every dictionary word that starts there and continue from where it ends.

2. Hint 2

   Plain backtracking wastes time on prefixes that can never be completed. First compute can[i] — whether s[i..] can be fully segmented — from right to left.

3. Hint 3

   Only step to a position j with can[j] true; then every branch of the search produces at least one sentence, so the work is proportional to the output. Sort the sentences at the end.

How to solve Word Break II

The number of sentences can be exponential, so the goal is a search whose cost is proportional to its output. A right-to-left Word Break table tells which suffixes are segmentable; the backtracking then never enters a dead end.

Approach

1. Put the dictionary in a hash set.
2. Compute can[n] = true and, for i from n - 1 down to 0, can[i] = true if some j > i has can[j] and s[i..j) in the set.
3. If can[0] is false, return an empty list.
4. Backtrack from i = 0 with a list of chosen words: at i == n, join the words with spaces and record the sentence; otherwise, for every j > i with can[j] and s[i..j) in the set, push the word, recurse at j, pop.
5. Sort the recorded sentences.

Why it works

Every sentence is a sequence of dictionary words that tiles s, and the search enumerates each tiling exactly once (the cut positions determine it). Restricting steps to positions with can[j] only removes branches that cannot reach the end, so no sentence is lost while every explored path ends in a recorded sentence.

Complexity

• Time — O(n^2 + total output length · n)
• Space — O(n) besides the output

Pitfalls

• Without the can pruning, inputs like aaaa…ab with dictionary a, aa, aaa explore exponentially many dead branches.
• The order is fixed: sort the final list (a space is smaller than any letter).
• Return an empty list, not a list with an empty sentence, when no segmentation exists.

Reference solution

Python

from typing import List

def wordBreak(s: str, wordDict: List[str]) -> List[str]:
    words = set(wordDict)
    n = len(s)
    can = [False] * (n + 1)
    can[n] = True
    for i in range(n - 1, -1, -1):
        for j in range(i + 1, n + 1):
            if can[j] and s[i:j] in words:
                can[i] = True
                break
    res = []
    parts = []

    def dfs(i):
        if i == n:
            res.append(" ".join(parts))
            return
        for j in range(i + 1, n + 1):
            if can[j] and s[i:j] in words:
                parts.append(s[i:j])
                dfs(j)
                parts.pop()

    if can[0]:
        dfs(0)
    res.sort()
    return res

Java

static void wbDfs(String s, int i, boolean[] can, Set<String> words, List<String> parts, List<String> res) {
    if (i == s.length()) {
        res.add(String.join(" ", parts));
        return;
    }
    for (int j = i + 1; j <= s.length(); j++) {
        if (can[j] && words.contains(s.substring(i, j))) {
            parts.add(s.substring(i, j));
            wbDfs(s, j, can, words, parts, res);
            parts.remove(parts.size() - 1);
        }
    }
}

public static String[] wordBreak(String s, String[] wordDict) {
    Set<String> words = new HashSet<>(Arrays.asList(wordDict));
    int n = s.length();
    boolean[] can = new boolean[n + 1];
    can[n] = true;
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i + 1; j <= n; j++) {
            if (can[j] && words.contains(s.substring(i, j))) {
                can[i] = true;
                break;
            }
        }
    }
    List<String> res = new ArrayList<>();
    if (can[0]) wbDfs(s, 0, can, words, new ArrayList<>(), res);
    Collections.sort(res);
    return res.toArray(new String[0]);
}

C++

static void wbDfs(const string& s, int i, const vector<bool>& can, const unordered_set<string>& words, vector<string>& parts, vector<string>& res) {
    int n = s.size();
    if (i == n) {
        string line;
        for (size_t k = 0; k < parts.size(); k++) {
            if (k) line += ' ';
            line += parts[k];
        }
        res.push_back(line);
        return;
    }
    for (int j = i + 1; j <= n; j++) {
        if (can[j] && words.count(s.substr(i, j - i))) {
            parts.push_back(s.substr(i, j - i));
            wbDfs(s, j, can, words, parts, res);
            parts.pop_back();
        }
    }
}

vector<string> wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> words(wordDict.begin(), wordDict.end());
    int n = s.size();
    vector<bool> can(n + 1, false);
    can[n] = true;
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i + 1; j <= n; j++) {
            if (can[j] && words.count(s.substr(i, j - i))) {
                can[i] = true;
                break;
            }
        }
    }
    vector<string> res, parts;
    if (can[0]) wbDfs(s, 0, can, words, parts, res);
    sort(res.begin(), res.end());
    return res;
}

JavaScript

var wordBreak = function(s, wordDict) {
    var words = new Set(wordDict);
    var n = s.length;
    var can = new Array(n + 1).fill(false);
    can[n] = true;
    for (var i = n - 1; i >= 0; i--) {
        for (var j = i + 1; j <= n; j++) {
            if (can[j] && words.has(s.substring(i, j))) {
                can[i] = true;
                break;
            }
        }
    }
    var res = [], parts = [];
    var dfs = function(i) {
        if (i === n) {
            res.push(parts.join(" "));
            return;
        }
        for (var j = i + 1; j <= n; j++) {
            if (can[j] && words.has(s.substring(i, j))) {
                parts.push(s.substring(i, j));
                dfs(j);
                parts.pop();
            }
        }
    };
    if (can[0]) dfs(0);
    res.sort();
    return res;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Design Movie Rental System Hard
• Dinner Plate Stacks Hard
• Prefix and Suffix Search Hard
• LFU Cache Hard
• Vertical Order Traversal of a Binary Tree Hard
• Maximum Number of Ways to Partition an Array Hard