【算法题】word-break-ii

àì夳堔傛蜴生んèń 2022-06-05 02:40 113阅读 0赞

此题是word-break的follow up，word-break用中规中矩的dp算法即可解决。

这个需要打印所有解决方案。

我用dp + dfs， leetcode和lintcode都可以通过。

时间复杂度：O(n方)

空间复杂度：O(n方)

题目：

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.

Return all such possible sentences.

For example, given  
s = `"catsanddog"`,  
dict = `["cat", "cats", "and", "sand", "dog"]`.

A solution is `["cats and dog", "cat sand dog"]`.

我的代码：

class Solution {
    public:
        vector<string> res;
        vector<vector<int>> dp;
        vector<string> wordBreak(string s, vector<string> &wordDict) {
            // write your code here
            
            if (s.size() == 0 || wordDict.size() == 0) {
                return res;
            }
            int maxLength = 0;
            for (auto w : wordDict) {
                maxLength = max(maxLength, (int)w.size());
            }
            for (int i = 0; i < s.size() + 1; i++) {
                dp.push_back(vector<int>());
            }
            dp[0].push_back(0);
            for (int i = 1; i < s.size() + 1; i++) {
                for (int j = 1; j <= i && j <= maxLength; j++) {
                    if (dp[i - j].size() != 0 && find(wordDict.begin(), wordDict.end(), s.substr(i - j, j)) != wordDict.end()) {
                        dp[i].push_back(i - j);
                    }
                }
            }
            for (int i = 0; i < dp[s.size()].size(); i++) {
                string res_element = "";
                help(s, res_element, s.size(), dp[s.size()][i]);
            }
            return res;
        }
        void help(string s, string res_element, int pos, int last_pos) {
            if (last_pos == 0) {
                res_element = s.substr(0, pos) + " " + res_element;
                res_element = res_element.substr(0, res_element.size() - 1);
                res.push_back(res_element);
                return;
            } 
            if (dp[last_pos].size() == 0) {
                return;
            }
            res_element = s.substr(last_pos, pos - last_pos) +" " + res_element;
            for (auto lp : dp[last_pos]) {
                help(s, res_element, last_pos, lp);
            }
            return;
        }
    };