[LeetCode] 140.Word Break II 拆分詞句之二

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

這道題是之前那道Word Break 拆分詞句的拓展，那道題只讓我們判斷給定的字符串能否被拆分成字典中的詞，而這道題加大了難度，讓我們求出所有可以拆分成的情況，就像題目中給的例子所示。之前的版本中字典wordDict的數(shù)據(jù)類型是HashSet，現(xiàn)在的不知為何改成了數(shù)組vector，而且博主看到第二個例子就笑了，PPAP么，哈哈～

根據(jù)老夫行走江湖多年的經(jīng)驗，像這種返回結(jié)果要列舉所有情況的題，十有八九都是要用遞歸來做的。當我們一時半會沒有啥思路的時候，先不要考慮代碼如何實現(xiàn)，如果就給你一個s和wordDict，不看Output的內(nèi)容，你會怎么找出結(jié)果。比如對于例子1，博主可能會先掃一遍wordDict數(shù)組，看有沒有單詞可以當s的開頭，那么我們可以發(fā)現(xiàn)cat和cats都可以，比如我們先選了cat，那么此時s就變成了 "sanddog"，我們再在數(shù)組里找單詞，發(fā)現(xiàn)了sand可以，最后剩一個dog，也在數(shù)組中，于是一個結(jié)果就出來了。然后回到開頭選cats的話，那么此時s就變成了 "anddog"，我們再在數(shù)組里找單詞，發(fā)現(xiàn)了and可以，最后剩一個dog，也在數(shù)組中，于是另一個結(jié)果也就出來了。那么這個查詢的方法很適合用遞歸來實現(xiàn)，因為s改變后，查詢的機制并不變，很適合調(diào)用遞歸函數(shù)。再者，我們要明確的是，如果不用記憶數(shù)組做減少重復(fù)計算的優(yōu)化，那么遞歸方法跟brute force沒什么區(qū)別，大概率無法通過OJ。所以我們要避免重復(fù)計算，如何避免呢，還是看上面的分析，如果當s變成 "sanddog"的時候，那么此時我們知道其可以拆分成sand和dog，當某個時候如果我們又遇到了這個 "sanddog"的時候，我們難道還需要再調(diào)用遞歸算一遍嗎，當然不希望啦，所以我們要將這個中間結(jié)果保存起來，由于我們必須要同時保存s和其所有的拆分的字符串，那么可以使用一個HashMap，來建立二者之間的映射，那么在遞歸函數(shù)中，我們首先檢測當前s是否已經(jīng)有映射，有的話直接返回即可，如果s為空了，我們?nèi)绾翁幚砟?，題目中說了給定的s不會為空，但是我們遞歸函數(shù)處理時s是會變空的，這時候我們是直接返回空集嗎，這里有個小trick，我們其實放一個空字符串返回，為啥要這么做呢？我們觀察題目中的Output，發(fā)現(xiàn)單詞之間是有空格，而最后一個單詞后面沒有空格，所以這個空字符串就起到了標記當前單詞是最后一個，那么我們就不要再加空格了。接著往下看，我們遍歷wordDict數(shù)組，如果某個單詞是s字符串中的開頭單詞的話，我們對后面部分調(diào)用遞歸函數(shù)，將結(jié)果保存到rem中，然后遍歷里面的所有字符串，和當前的單詞拼接起來，這里就用到了我們前面說的trick。for循環(huán)結(jié)束后，記得返回結(jié)果res之前建立其和s之間的映射，方便下次使用，參見代碼如下：

解法一：

class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        unordered_map<string, vector<string>> m;
        return helper(s, wordDict, m);
    }
    vector<string> helper(string s, vector<string>& wordDict, unordered_map<string, vector<string>>& m) {
        if (m.count(s)) return m[s];
        if (s.empty()) return {""};
        vector<string> res;
        for (string word : wordDict) {
            if (s.substr(0, word.size()) != word) continue;
            vector<string> rem = helper(s.substr(word.size()), wordDict, m);
            for (string str : rem) {
                res.push_back(word + (str.empty() ? "" : " ") + str);
            }
        }
        return m[s] = res;
    }
};

我們也可以將將主函數(shù)本身當作遞歸函數(shù)，這樣就不用單獨的使用一個遞歸函數(shù)了，不過我們的HashMap必須是全局了，寫在外部就好了，參見代碼如下：

解法二：

class Solution {
public:
    unordered_map<string, vector<string>> m;
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        if (m.count(s)) return m[s];
        if (s.empty()) return {""};
        vector<string> res;
        for (string word : wordDict) {
            if (s.substr(0, word.size()) != word) continue;
            vector<string> rem = wordBreak(s.substr(word.size()), wordDict);
            for (string str : rem) {
                res.push_back(word + (str.empty() ? "" : " ") + str);
            }
        }
        return m[s] = res;
    }
};

類似題目：

Word Break

Concatenated Words

參考資料：

https://leetcode.com/problems/word-break-ii/description/

https://leetcode.com/problems/word-break-ii/solution/

https://leetcode.com/problems/word-break-ii/discuss/44167/My-concise-JAVA-solution-based-on-memorized-DFS

到此這篇關(guān)于C++實現(xiàn)LeetCode(140.拆分詞句之二)的文章就介紹到這了,更多相關(guān)C++實現(xiàn)拆分詞句之二內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！