Given anon-emptystringsand a dictionarywordDictcontaining a list ofnon-emptywords, add spaces insto construct a sentence where each word is a valid dictionary word.Return all such possible sentences.

Note:

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

You may assume the dictionary does not contain duplicate words.

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:
[]

139. Word break is an extension of word break. That question is just to judge whether it can be split, and this question requires the output of all possible split combinations.

Solution: DP + DFS, first use DP to calculate whether it can be split, and then use DFS to find the specific split combination.

Java:

public static List<String&> wordBreak(String s, Set<String&> dict) {
    //create an array of ArrayList<String&>
    List<String&> dp[] = new ArrayList[s.length()+1];
    dp[0] = new ArrayList<String&>();
 
    for(int i=0; i<s.length(); i++){
        if( dp[i] == null ) 
            continue; 
 
        for(String word:dict){
            int len = word.length();
            int end = i+len;
            if(end &> s.length()) 
                continue;
 
            if(s.substring(i,end).equals(word)){
                if(dp[end] == null){
                    dp[end] = new ArrayList<String&>();
                }
                dp[end].add(word);
            }
        }
    }
 
    List<String&> result = new LinkedList<String&>();
    if(dp[s.length()] == null) 
        return result; 
 
    ArrayList<String&> temp = new ArrayList<String&>();
    dfs(dp, s.length(), result, temp);
 
    return result;
}
 
public static void dfs(List<String&> dp[],int end,List<String&> result, ArrayList<String&> tmp){
    if(end <= 0){
        String path = tmp.get(tmp.size()-1);
        for(int i=tmp.size()-2; i&>=0; i--){
            path += " " + tmp.get(i) ;
        }
 
        result.add(path);
        return;
    }
 
    for(String str : dp[end]){
        tmp.add(str);
        dfs(dp, end-str.length(), result, tmp);
        tmp.remove(tmp.size()-1);
    }
}

Java:

public List<String&> wordBreak(String s, Set<String&> wordDict) {
    ArrayList<String&> [] pos = new ArrayList[s.length()+1];
    pos[0]=new ArrayList<String&>();
 
    for(int i=0; i<s.length(); i++){
        if(pos[i]!=null){
            for(int j=i+1; j<=s.length(); j++){
                String sub = s.substring(i,j);
                if(wordDict.contains(sub)){
                    if(pos[j]==null){
                        ArrayList<String&> list = new ArrayList<String&>();
                        list.add(sub);
                        pos[j]=list;
                    }else{
                        pos[j].add(sub);
                    }
 
                }
            }
        }
    }
 
    if(pos[s.length()]==null){
        return new ArrayList<String&>();
    }else{
        ArrayList<String&> result = new ArrayList<String&>();
        dfs(pos, result, "", s.length());
        return result;
    }
}
 
public void dfs(ArrayList<String&> [] pos, ArrayList<String&> result, String curr, int i){
    if(i==0){
        result.add(curr.trim());
        return;
    }
 
    for(String s: pos[i]){
        String combined = s + " "+ curr;
        dfs(pos, result, combined, i-s.length());
    }
}　

Java:

public class Solution {
    Map<String, List<String&>&> done = new HashMap<&>();
    Set<String&> dict;

    public List<String&> wordBreak(String s, Set<String&> dict) {
        this.dict = dict;
        done.put("", new ArrayList<&>());
        done.get("").add("");

        return dfs(s);
    }

    List<String&> dfs(String s) {
        if (done.containsKey(s)) {
            return done.get(s);
        }
        List<String&> ans = new ArrayList<&>();

        for (int len = 1; len <= s.length(); len++) { 
            String s1 = s.substring(0, len);
            String s2 = s.substring(len);

            if (dict.contains(s1)) {
                List<String&> s2_res = dfs(s2);
                for (String item : s2_res) {
                    if (item == "") {
                        ans.add(s1);
                    } else {
                        ans.add(s1 + " " + item);
                    }
                }
            }
        }
        done.put(s, ans);
        return ans;
    }
}　

Python:

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: Set[str]
        :rtype: List[str]
        """
        n = len(s)

        max_len = 0
        for string in wordDict:
            max_len = max(max_len, len(string))

        can_break = [False for _ in xrange(n + 1)]
        valid = [[False] * n for _ in xrange(n)]
        can_break[0] = True
        for i in xrange(1, n + 1):
            for l in xrange(1, min(i, max_len) + 1):
                if can_break[i-l] and s[i-l:i] in wordDict:
                    valid[i-l][i-1] = True
                    can_break[i] = True

        result = []
        if can_break[-1]:
            self.wordBreakHelper(s, valid, 0, [], result)
        return result

    def wordBreakHelper(self, s, valid, start, path, result):
        if start == len(s):
            result.append(" ".join(path))
            return
        for i in xrange(start, len(s)):
            if valid[start][i]:
                path += [s[start:i+1]]
                self.wordBreakHelper(s, valid, i + 1, path, result)
                path.pop()　

C++:

class Solution {
public:
    vector<string&> wordBreak(string s, unordered_set<string&>& wordDict) {
        vector<string&> res;
        string out;
        vector<bool&> possible(s.size() + 1, true);
        wordBreakDFS(s, wordDict, 0, possible, out, res);
        return res;
    }
    void wordBreakDFS(string &s, unordered_set<string&> &wordDict, int start, vector<bool&> &possible, string &out, vector<string&> &res) {
        if (start == s.size()) {
            res.push_back(out.substr(0, out.size() - 1));
            return;
        }
        for (int i = start; i < s.size(); ++i) {
            string word = s.substr(start, i - start + 1);
            if (wordDict.find(word) != wordDict.end() && possible[i + 1]) {
                out.append(word).append(" ");
                int oldSize = res.size();
                wordBreakDFS(s, wordDict, i + 1, possible, out, res);
                if (res.size() == oldSize) possible[i + 1] = false;
                out.resize(out.size() - word.size() - 1);
            }
        }
    }
};

>>

Similar theme:

[LeetCode] 139. Word Break units break

All LeetCode Questions List Total