Leetcode.140.Word Break II

题目

给定一个句子和一组单词, 单词可以重复, 列出单词组成句子的情况.

Input: "catsanddog", ["cat", "cats", "and", "sand", "dog"]
Output: ["cats and dog", "cat sand dog"]
Input: "pineapplepenapple", ["apple", "pen", "applepen", "pine", "pineapple"]
Output: ["pine apple pen apple", "pineapple pen apple", "pine applepen apple"]
Input: "aaaaaaa", ["aaaa","aaa"]
Output: ["aaa aaaa", "aaaa aaa"]

思路1

递归.效率低.

void wordBreakHelper(string& str, vector<string>& words, int index, string temp,vector<string>& res) {
    if (index == str.size()) {
        if (!temp.empty()) {
            temp = temp.substr(1);
        }
        res.push_back(temp);
    } else if (index < str.size()) {
        for (string word : words) {
            int len = (int)word.size();
            string subStr = str.substr(index,word.size());
            if (word == subStr) {
                wordBreakHelper(str, words, index + len, temp+" "+word,res);
            }
        }
    }
}

vector<string> wordBreak2(string s, vector<string>& words) {
    vector<string> res;
    wordBreakHelper(s, words, 0, "", res);
    return res;
}

思路2

DFS.计算出空格的位置.

void wordBreakDFS(string& s, const vector<unordered_set<int>>& vec, int i, vector<string>& res) {
    if (i < s.size()) {
        s.insert(i, 1, ' ');
    }
    for (int next : vec[i]) {
        if (next == 0) {
            res.push_back(s);
        }else {
            wordBreakDFS(s,vec,next,res);
        }
    }

    if (i < s.size()) {
        s.erase(i,1);
    }
}

vector<string> wordBreak(string s, vector<string>& words) {
    unordered_set<int> lens;
    unordered_set<string> dict;
       for (int i(0); i < words.size(); ++i) {
        lens.insert((int)words[i].size());
        dict.insert(words[i]);
    }

    int n = (int)s.size();
    vector<unordered_set<int>> dp(n+1, unordered_set<int>());
    for (int i = 1; i <= n; i++) {
        for (int l : lens) {
            if (l <= i) {
                string word = s.substr(i-l,l);
                if (dict.count(word)) {
                    if (l == i || !dp[i-l].empty()) {
                        dp[i].insert(i-l);
                    }
               }
           }
        }
    }
    vector<string> rst;
    wordBreakDFS(s, dp, n, rst);
    return rst;
}

总结

转换思维, 可以计算空格的位置更为简单.