C++實現LeetCode(140.拆分詞句之二)

[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的數據類型是HashSet,現在的不知為何改成瞭數組vector,而且博主看到第二個例子就笑瞭,PPAP麼,哈哈~

根據老夫行走江湖多年的經驗,像這種返回結果要列舉所有情況的題,十有八九都是要用遞歸來做的。當我們一時半會沒有啥思路的時候,先不要考慮代碼如何實現,如果就給你一個s和wordDict,不看Output的內容,你會怎麼找出結果。比如對於例子1,博主可能會先掃一遍wordDict數組,看有沒有單詞可以當s的開頭,那麼我們可以發現cat和cats都可以,比如我們先選瞭cat,那麼此時s就變成瞭 “sanddog”,我們再在數組裡找單詞,發現瞭sand可以,最後剩一個dog,也在數組中,於是一個結果就出來瞭。然後回到開頭選cats的話,那麼此時s就變成瞭 “anddog”,我們再在數組裡找單詞,發現瞭and可以,最後剩一個dog,也在數組中,於是另一個結果也就出來瞭。那麼這個查詢的方法很適合用遞歸來實現,因為s改變後,查詢的機制並不變,很適合調用遞歸函數。再者,我們要明確的是,如果不用記憶數組做減少重復計算的優化,那麼遞歸方法跟brute force沒什麼區別,大概率無法通過OJ。所以我們要避免重復計算,如何避免呢,還是看上面的分析,如果當s變成 ”sanddog”的時候,那麼此時我們知道其可以拆分成sand和dog,當某個時候如果我們又遇到瞭這個 ”sanddog”的時候,我們難道還需要再調用遞歸算一遍嗎,當然不希望啦,所以我們要將這個中間結果保存起來,由於我們必須要同時保存s和其所有的拆分的字符串,那麼可以使用一個HashMap,來建立二者之間的映射,那麼在遞歸函數中,我們首先檢測當前s是否已經有映射,有的話直接返回即可,如果s為空瞭,我們如何處理呢,題目中說瞭給定的s不會為空,但是我們遞歸函數處理時s是會變空的,這時候我們是直接返回空集嗎,這裡有個小trick,我們其實放一個空字符串返回,為啥要這麼做呢?我們觀察題目中的Output,發現單詞之間是有空格,而最後一個單詞後面沒有空格,所以這個空字符串就起到瞭標記當前單詞是最後一個,那麼我們就不要再加空格瞭。接著往下看,我們遍歷wordDict數組,如果某個單詞是s字符串中的開頭單詞的話,我們對後面部分調用遞歸函數,將結果保存到rem中,然後遍歷裡面的所有字符串,和當前的單詞拼接起來,這裡就用到瞭我們前面說的trick。for循環結束後,記得返回結果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;
    }
};

我們也可以將將主函數本身當作遞歸函數,這樣就不用單獨的使用一個遞歸函數瞭,不過我們的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

到此這篇關於C++實現LeetCode(140.拆分詞句之二)的文章就介紹到這瞭,更多相關C++實現拆分詞句之二內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!

推薦閱讀: