（每日一练C++）140. 单词拆分 II

拼搏现实的明天。 2023-10-04 18:31 29阅读 0赞

给定一个字符串 s 和一个字符串字典 wordDict ，在字符串 s 中增加空格来构建一个句子，使得句子中所有的单词都在词典中。以任意顺序 返回所有这些可能的句子。

注意：词典中的同一个单词可能在分段中被重复使用多次。

示例 1：

输入:s = "catsanddog", wordDict = \["cat","cats","and","sand","dog"\]  
输出:\["cats and dog","cat sand dog"\]  
示例 2：

输入:s = "pineapplepenapple", wordDict = \["apple","pen","applepen","pine","pineapple"\]  
输出:\["pine apple pen apple","pineapple pen apple","pine applepen apple"\]  
解释: 注意你可以重复使用字典中的单词。  
示例 3：

输入:s = "catsandog", wordDict = \["cats","dog","sand","and","cat"\]  
输出:\[\]

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/word-break-ii  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    private:
        unordered_map<int, vector<string>> ans;
        unordered_set<string> wordSet;
    
    public:
        vector<string> wordBreak(string s, vector<string>& wordDict) {
            wordSet = unordered_set(wordDict.begin(), wordDict.end());
            backtrack(s, 0);
            return ans[0];
        }
    
        void backtrack(const string& s, int index) {
            if (!ans.count(index)) {
                if (index == s.size()) {
                    ans[index] = {""};
                    return;
                }
                ans[index] = {};
                for (int i = index + 1; i <= s.size(); ++i) {
                    string word = s.substr(index, i - index);
                    if (wordSet.count(word)) {
                        backtrack(s, i);
                        for (const string& succ: ans[i]) {
                            ans[index].push_back(succ.empty() ? word : word + " " + succ);
                        }
                    }
                }
            }
        }
    };
    
    作者：LeetCode-Solution
    链接：https://leetcode-cn.com/problems/word-break-ii/solution/dan-ci-chai-fen-ii-by-leetcode-solution/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。