[LeetCode] 139. Word Break 拆分詞句

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

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 = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because

"leetcode"

can be segmented as

"leet code"

.

Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because

"

applepenapple

"

can be segmented as

"

apple pen apple

"

.

             Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

這道拆分詞句問題是看給定的詞句能分被拆分成字典里面的內容，這是一道很經典的題目，解法不止一種，考察的范圍很廣，屬于我們必須要熟練掌握的題目。那么先來想 brute force 的解法，就拿例子1來分析，如果字典中只有兩個單詞，我們怎么去判斷，是不是可以將原字符串s分成任意兩段，然后再看分成的單詞是否在字典中。注意這道題說是單詞可以重復使用，所以可以分成任意段，而且字典中的單詞可以有很多個，這就增加了題目的難度，很多童鞋就在這里迷失了，毫無頭緒。

既然要分段，看子字符串是否在字典中，由于給定的字典是數(shù)組（之前還是 HashSet 呢），那么我們肯定不希望每次查找都需要遍歷一遍數(shù)組，費勁！還是把字典中的所有單詞都存入 HashSet 中吧，這樣我們就有了常數(shù)時間級的查找速度，perfect！好，我們得開始給字符串分段了，怎么分，只能一個一個分了，先看第一個字母是否在字典中，如果不在的話，好辦，說明這種分法肯定是錯的。問題是在的話，后面的那部分怎么處理，難道還用 for 循環(huán)？咱也不知道還要分多少段，怎么用 for 循環(huán)。對于這種不知道怎么處理的情況，一個萬能的做法是丟給遞歸函數(shù)，讓其去遞歸求解，這里我們 suppose 遞歸函數(shù)會返回我們一個正確的值，如果返回的是 true 的話，表明我們現(xiàn)在分成的兩段都在字典中，我們直接返回 true 即可，因為只要找出一種情況就行了。這種調用遞歸函數(shù)的方法就是 brute force 的解法，我們遍歷了所有的情況，優(yōu)點是寫法簡潔，思路清晰，缺點是存在大量的重復計算，被 OJ 啪啪打臉。所以我們需要進行優(yōu)化，使用記憶數(shù)組 memo 來保存所有已經計算過的結果，再下次遇到的時候，直接從 cache 中取，而不是再次計算一遍。這種使用記憶數(shù)組 memo 的遞歸寫法，和使用 dp 數(shù)組的迭代寫法，乃解題的兩大神器，凡事能用 dp 解的題，一般也有用記憶數(shù)組的遞歸解法，好似一對形影不離的好基友～關于 dp 解法，博主會在下文中講解。這里我們的記憶數(shù)組 memo[i] 定義為范圍為 [i, n] 的子字符串是否可以拆分，初始化為 -1，表示沒有計算過，如果可以拆分，則賦值為1，反之為0。在之前講 brute force 解法時，博主提到的是講分成兩段的后半段的調用遞歸函數(shù)，我們也可以不取出子字符串，而是用一個 start 變量，來標記分段的位置，這樣遞歸函數(shù)中只需要從 start 的位置往后遍歷即可，在遞歸函數(shù)更新記憶數(shù)組 memo 即可，參見代碼如下：

解法一：

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        vector<int> memo(s.size(), -1);
        return check(s, wordSet, 0, memo);
    }
    bool check(string s, unordered_set<string>& wordSet, int start, vector<int>& memo) {
        if (start >= s.size()) return true;
        if (memo[start] != -1) return memo[start];
        for (int i = start + 1; i <= s.size(); ++i) {
            if (wordSet.count(s.substr(start, i - start)) && check(s, wordSet, i, memo)) {
                return memo[start] = 1;
            }
        }
        return memo[start] = 0;
    }
};

這道題其實還是一道經典的 DP 題目，也就是動態(tài)規(guī)劃 Dynamic Programming。博主曾經說玩子數(shù)組或者子字符串且求極值的題，基本就是 DP 沒差了，雖然這道題沒有求極值，但是玩子字符串也符合 DP 的狀態(tài)轉移的特點。把一個人的溫暖轉移到另一個人的胸膛... 咳咳，跑錯片場了，那是愛情轉移～ 強行拉回，DP 解法的兩大難點，定義 dp 數(shù)組跟找出狀態(tài)轉移方程，先來看 dp 數(shù)組的定義，這里我們就用一個一維的 dp 數(shù)組，其中 dp[i] 表示范圍 [0, i) 內的子串是否可以拆分，注意這里 dp 數(shù)組的長度比s串的長度大1，是因為我們要 handle 空串的情況，我們初始化 dp[0] 為 true，然后開始遍歷。注意這里我們需要兩個 for 循環(huán)來遍歷，因為此時已經沒有遞歸函數(shù)了，所以我們必須要遍歷所有的子串，我們用j把 [0, i) 范圍內的子串分為了兩部分，[0, j) 和 [j, i)，其中范圍 [0, j) 就是 dp[j]，范圍 [j, i) 就是 s.substr(j, i-j)，其中 dp[j] 是之前的狀態(tài)，我們已經算出來了，可以直接取，只需要在字典中查找 s.substr(j, i-j) 是否存在了，如果二者均為 true，將 dp[i] 賦為 true，并且 break 掉，此時就不需要再用j去分 [0, i) 范圍了，因為 [0, i) 范圍已經可以拆分了。最終我們返回 dp 數(shù)組的最后一個值，就是整個數(shù)組是否可以拆分的布爾值了，代碼如下：

解法二：

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        vector<bool> dp(s.size() + 1);
        dp[0] = true;
        for (int i = 0; i < dp.size(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (dp[j] && wordSet.count(s.substr(j, i - j))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp.back();
    }
};

下面我們從題目中給的例子來分析：

l 

le e 

lee ee e 

leet 

leetc eetc etc tc c 

leetco eetco etco tco co o 

leetcod eetcod etcod tcod cod od d 

leetcode eetcode etcode tcode code 

T F F F T F F F T 

我們知道算法的核心思想是逐行掃描，每一行再逐個字符掃描，每次都在組合出一個新的字符串都要到字典里去找，如果有的話，則跳過此行，繼續(xù)掃描下一行。

既然 DFS 都可以解題，那么 BFS 也就坐不住了，也要出來蹦跶一下。其實本質跟遞歸的解法沒有太大的區(qū)別，遞歸解法在調用遞歸的時候，原先的狀態(tài)被存入了棧中，這里 BFS 是存入了隊列中，使用 visited 數(shù)組來標記已經算過的位置，作用跟 memo 數(shù)組一樣，從隊列中取出一個位置進行遍歷，把可以拆分的新位置存入隊列中，遍歷完成后標記當前位置，然后再到隊列中去取即可，參見代碼如下：

解法三：

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        vector<bool> visited(s.size());
        queue<int> q{{0}};
        while (!q.empty()) {
            int start = q.front(); q.pop();
            if (!visited[start]) {
                for (int i = start + 1; i <= s.size(); ++i) {
                    if (wordSet.count(s.substr(start, i - start))) {
                        q.push(i);
                        if (i == s.size()) return true;
                    }
                }
                visited[start] = true;
            }
        }
        return false;
    }
};

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

最新評論