C++實現LeetCode(139.拆分詞句)

Posted on by

[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分成任意兩段，然後再看分成的單詞是否在字典中。註意這道題說是單詞可以重復使用，所以可以分成任意段，而且字典中的單詞可以有很多個，這就增加瞭題目的難度，很多童鞋就在這裡迷失瞭，毫無頭緒。

既然要分段，看子字符串是否在字典中，由於給定的字典是數組（之前還是 HashSet 呢），那麼我們肯定不希望每次查找都需要遍歷一遍數組，費勁！還是把字典中的所有單詞都存入 HashSet 中吧，這樣我們就有瞭常數時間級的查找速度，perfect！好，我們得開始給字符串分段瞭，怎麼分，隻能一個一個分瞭，先看第一個字母是否在字典中，如果不在的話，好辦，說明這種分法肯定是錯的。問題是在的話，後面的那部分怎麼處理，難道還用 for 循環？咱也不知道還要分多少段，怎麼用 for 循環。對於這種不知道怎麼處理的情況，一個萬能的做法是丟給遞歸函數，讓其去遞歸求解，這裡我們 suppose 遞歸函數會返回我們一個正確的值，如果返回的是 true 的話，表明我們現在分成的兩段都在字典中，我們直接返回 true 即可，因為隻要找出一種情況就行瞭。這種調用遞歸函數的方法就是 brute force 的解法，我們遍歷瞭所有的情況，優點是寫法簡潔，思路清晰，缺點是存在大量的重復計算，被 OJ 啪啪打臉。所以我們需要進行優化，使用記憶數組 memo 來保存所有已經計算過的結果，再下次遇到的時候，直接從 cache 中取，而不是再次計算一遍。這種使用記憶數組 memo 的遞歸寫法，和使用 dp 數組的迭代寫法，乃解題的兩大神器，凡事能用 dp 解的題，一般也有用記憶數組的遞歸解法，好似一對形影不離的好基友～關於 dp 解法，博主會在下文中講解。這裡我們的記憶數組 memo[i] 定義為范圍為 [i, n] 的子字符串是否可以拆分，初始化為 -1，表示沒有計算過，如果可以拆分，則賦值為1，反之為0。在之前講 brute force 解法時，博主提到的是講分成兩段的後半段的調用遞歸函數，我們也可以不取出子字符串，而是用一個 start 變量，來標記分段的位置，這樣遞歸函數中隻需要從 start 的位置往後遍歷即可，在遞歸函數更新記憶數組 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 題目，也就是動態規劃 Dynamic Programming。博主曾經說玩子數組或者子字符串且求極值的題，基本就是 DP 沒差瞭，雖然這道題沒有求極值，但是玩子字符串也符合 DP 的狀態轉移的特點。把一個人的溫暖轉移到另一個人的胸膛… 咳咳，跑錯片場瞭，那是愛情轉移～ 強行拉回，DP 解法的兩大難點，定義 dp 數組跟找出狀態轉移方程，先來看 dp 數組的定義，這裡我們就用一個一維的 dp 數組，其中 dp[i] 表示范圍 [0, i) 內的子串是否可以拆分，註意這裡 dp 數組的長度比s串的長度大1，是因為我們要 handle 空串的情況，我們初始化 dp[0] 為 true，然後開始遍歷。註意這裡我們需要兩個 for 循環來遍歷，因為此時已經沒有遞歸函數瞭，所以我們必須要遍歷所有的子串，我們用j把 [0, i) 范圍內的子串分為瞭兩部分，[0, j) 和 [j, i)，其中范圍 [0, j) 就是 dp[j]，范圍 [j, i) 就是 s.substr(j, i-j)，其中 dp[j] 是之前的狀態，我們已經算出來瞭，可以直接取，隻需要在字典中查找 s.substr(j, i-j) 是否存在瞭，如果二者均為 true，將 dp[i] 賦為 true，並且 break 掉，此時就不需要再用j去分 [0, i) 范圍瞭，因為 [0, i) 范圍已經可以拆分瞭。最終我們返回 dp 數組的最後一個值，就是整個數組是否可以拆分的佈爾值瞭，代碼如下：

解法二：

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 

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

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

解法三：

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++實現LeetCode(139.拆分詞句)的文章就介紹到這瞭,更多相關C++實現拆分詞句內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：