[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

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

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

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

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

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

解法三：

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;
    }
};

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

最新評(píng)論