140

140. Word Break II (Hard)

Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

 

Example 1:

Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]

Example 2:

Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"]
Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: []

 

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.
• Input is generated in a way that the length of the answer doesn't exceed 10⁵.

Companies: Bloomberg, Google, Facebook, Amazon, Apple, Microsoft, Uber, Grammarly, Adobe, Snapchat, Audible, Twitter, Dropbox

Related Topics:
Array, Hash Table, String, Dynamic Programming, Backtracking, Trie, Memoization

Similar Questions:

• Word Break (Medium)
• Concatenated Words (Hard)

Solution 1.

// OJ: https://leetcode.com/problems/word-break-ii/
// Author: github.com/lzl124631x
// Time: O(N!)
// Space: O(N + D)
class Solution {
    vector<string> ans, tmp;
    unordered_set<string> st;
    void dfs(string &s, int i) {
        if (i == s.size()) {
            string n;
            for (auto &t : tmp) {
                n += (n.size() ? " " : "") + t;
            }
            ans.push_back(n);
        }
        for (int j = i + 1; j <= s.size(); ++j) {
            auto sub = s.substr(i, j - i);
            if (st.count(sub) == 0) continue;
            tmp.push_back(sub);
            dfs(s, j);
            tmp.pop_back();
        }
    }
public:
    vector<string> wordBreak(string s, vector<string>& dict) {
        st = unordered_set<string>(begin(dict), end(dict));
        dfs(s, 0);
        return ans;
    }
};

Or use Trie

// OJ: https://leetcode.com/problems/word-break-ii
// Author: github.com/lzl124631x
// Time: O(N!)
// Space: O(N + D)
struct TrieNode {
    TrieNode *next[26] = {};
    bool end = false;
};
class Solution {
    void addWord(TrieNode *node, string &s) {
        for (char c : s) {
            if (!node->next[c - 'a']) node->next[c - 'a'] = new TrieNode();
            node = node->next[c - 'a'];
        }
        node->end = true;
    }
public:
    vector<string> wordBreak(string s, vector<string>& A) {
        vector<string> ans, tmp;
        TrieNode root;
        for (auto &w : A) addWord(&root, w);
        int N = s.size();
        function<void(int)> dfs = [&](int i) {
            if (i == N) {
                string line;
                for (auto &w : tmp) {
                    if (line.size()) line += ' ';
                    line += w;
                }
                ans.push_back(line);
                return;
            }
            auto node = &root;
            int start = i;
            while (i < N && node->next[s[i] - 'a']) {
                node = node->next[s[i] - 'a'];
                ++i;
                if (node->end) {
                    tmp.push_back(s.substr(start, i - start));
                    dfs(i);
                    tmp.pop_back();
                }
            }
        };
        dfs(0);
        return ans;
    }
};

Solution 2. Backtracking

One optimization is that we can store dp[i] meaning if we can reach the end from index i. If we know that we can't from i, we can skip it.

// OJ: https://leetcode.com/problems/word-break-ii/
// Author: github.com/lzl124631x
// Time: O(N!)
// Space: O(N + D)
class Solution {
    vector<string> ans, tmp;
    unordered_set<string> st;
    vector<int> dp; // -1 unvisited, 0 can't reach end, 1 can reach end
    bool dfs(string &s, int i) {
        if (i == s.size()) {
            string n;
            for (auto &t : tmp) {
                n += (n.size() ? " " : "") + t;
            }
            ans.push_back(n);
            return true;
        }
        for (int j = i + 1; j <= s.size(); ++j) {
            if (dp[j] == 0) continue;
            auto sub = s.substr(i, j - i);
            if (st.count(sub) == 0) continue;
            tmp.push_back(sub);
            if (dfs(s, j)) dp[i] = 1;
            tmp.pop_back();
        }
        return dp[i];
    }
public:
    vector<string> wordBreak(string s, vector<string>& dict) {
        st = unordered_set<string>(begin(dict), end(dict));
        dp.assign(s.size() + 1, -1);
        dp[s.size()] = 1;
        dfs(s, 0);
        return ans;
    }
};