Word Break II

• Lintcode : 582 / Leetcode : 140
• Level : Hard

Problem

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

Example
Example 1:

Input："lintcode"，["de","ding","co","code","lint"]
Output：["lint code", "lint co de"]
Explanation：
insert a space is "lint code"，insert two spaces is "lint co de".
Example 2:

Input："a"，[]
Output：[]
Explanation：dict is null.

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time :
space:

Answer

class Solution {
public:
    vector<string> wordBreak(string &s, unordered_set<string> &wordDict) {
        unordered_map<string, vector<string>> memo;
        return dfs(s, wordDict, memo);
    }
private:
    vector<string> dfs(string s, unordered_set<string> &wordDict,unordered_map<string, vector<string>> &memo) {
        if (s.empty()) return {""};
        if (memo.find(s) != memo.end()) return memo[s];
        vector<string> res;
        for (int i = 1; i <= s.length(); i++) {
            string temp = s.substr(0, i);
            if (wordDict.find(temp) == wordDict.end()) continue;
            vector<string> coms = dfs(s.substr(i), wordDict, memo);
            for (auto com : coms) {
                if (i == s.length())
                    res.push_back(temp);
                else
                    res.push_back(temp + " " + com);
            }
        }
        memo[s] = res;
        return memo[s];
    }
};

tags: DP

​