單詞拆分

力扣題目鏈接(opens new window)

給定一個非空字符串 s 和一個包含非空單詞的列表 wordDict，判定 s 是否可以被空格拆分為一個或多個在字典中出現(xiàn)的單詞。

說明：

拆分時可以重復(fù)使用字典中的單詞。

你可以假設(shè)字典中沒有重復(fù)的單詞。

示例 1：

• 輸入: s = "leetcode", wordDict = ["leet", "code"]
• 輸出: true
• 解釋: 返回 true 因為 "leetcode" 可以被拆分成 "leet code"。

示例 2：

• 輸入: s = "applepenapple", wordDict = ["apple", "pen"]
• 輸出: true
• 解釋: 返回 true 因為 "applepenapple" 可以被拆分成 "apple pen apple"。
• 注意你可以重復(fù)使用字典中的單詞。

示例 3：

• 輸入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
• 輸出: false

思路

如果要往背包問題上靠的話，可以把wordDict中的單詞視為"物品"，把字符串s的長度視為背包容量（注意，這里說的是長度，即s.size）

思路聽上去很常規(guī),但是具體到實現(xiàn)方式上就有點復(fù)雜

五步走

1、確定dp數(shù)組含義

如果拿不準(zhǔn)dp數(shù)組中的元素是什么類型，可以看看題目的示例返回的是什么類型的值，那一般就是需要找的值

這里題目要判定字典wordDict中的單詞能不能拼成字符串s

那么實現(xiàn)過程中肯定要用字典wordDict中的單詞與當(dāng)前遍歷區(qū)間內(nèi)截取到的子串進(jìn)行比較，要么相同要么不同，再結(jié)合示例的返回值，可以判斷dp數(shù)組中的值應(yīng)該是布爾類型

回到正題，dp數(shù)組究竟代表什么意思

假設(shè)有一個長度為i的字符串s的子串，若dp[i] = true

那么dp[i]表示該字符串可以拆分為1個或多個字典wordDict中的單詞（可以理解為：dp[i]是對遍歷過程中某個子串是否能拆分為wordDict中單詞的一個認(rèn)證，true就是能拆，false就是拆不了）

2+3、確定遞推公式和初始化dp數(shù)組

這個遞推公式的條件可太多了，為什么連起來一塊說，看到后面就知道了

首先，因為我們要不斷遍歷字符串s并截取子串，通過查找子串是否存在于字典wordDict中來判斷當(dāng)前子串是否可以拆分

為什么要判斷子串是否可以拆分？

因為一旦遍歷完字符串s，那么此時的子串就是s本身了。進(jìn)而就可以求s能不能被拆分為字典wordDict中的單詞，這里體現(xiàn)了dp的思想，即前一輪遍歷的子串會影響下一輪的，最終影響整個結(jié)果

所以，第一個條件是：所遍歷區(qū)間內(nèi)的子串必須出現(xiàn)在字典中

在說第二個條件之前，有必要說一下 "不斷遍歷字符串s并截取子串" 的實現(xiàn)方式

其實就是雙指針

		for (int i = 1; i <= s.size(); i++) {   // 遍歷背包
            for (int j = 0; j < i; j++) {       // 遍歷物品
                string word = s.substr(j, i - j); //substr(起始位置，截取的個數(shù))
                if (wordSet.find(word) != wordSet.end() && dp[j]) {//這里wordSet是一個unordered_set
                    dp[i] = true;
                }
            }
        }

下面用圖來解釋一下遍歷過程

上圖推導(dǎo)了兩層for循環(huán)的遍歷過程，其中，外層for循環(huán)負(fù)責(zé)遍歷字符串s（也就是所謂的背包），而內(nèi)層for則用來在[j,i]區(qū)間內(nèi)遍歷所有該區(qū)域內(nèi)的子串，用來在wordSet中查詢

如圖所示，當(dāng)外層for遍歷到 i = 4 ，才獲取到第一個能在wordSet中查詢到的子串"leet"

為什么不是在i = 3時得到？ 因為substr函數(shù)截取子串的區(qū)間時左閉右開的，詳見 題外話

注意j遍歷截取區(qū)間[j,i]內(nèi)所有子串的順序：它是先截最長的（如圖所示）

此時，如果我們將dp[0]初始化為true

那么，每次i移動的時候，j重置為0，dp[j]就為true

若本次i移動到的位置，在j第一次獲取子串時就能獲取到目標(biāo)子串的話，其實就找到了一個滿足條件的子串

所以，此時的dp[i]也應(yīng)該為true

因此，第二個條件就是：[j, i] 這個區(qū)間的子串是否出現(xiàn)在字典里

綜上所述，本題的遞推公式是： if([j, i] 這個區(qū)間的子串出現(xiàn)在字典里 && dp[j]是true) 那么 dp[i] = true。（j < i ）

初始化就是dp[0] = true（我認(rèn)為完全是為了代碼實現(xiàn)考慮，沒有別的含義），其余位置是false

4、確定遍歷順序

因為題目說了，字符串s中可能會有"一個或多個"能夠拆分為字典中單詞的子串，也就是說背包中可以放多個相同的物品（單詞），所以這是一個完全背包問題

而構(gòu)成子串必須按一定順序才能構(gòu)成字符串s，所以本題的完全背包求的是排序（排列有序組合無序）（排列組合的區(qū)別詳見）

所以遍歷順序是：先背包容量后物品

代碼

太繞了，終于到代碼了文章來源地址http://www.zghlxwxcb.cn/news/detail-419714.html

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        //定義dp數(shù)組
        vector<bool> dp(s.size() + 1, false);
        //初始化
        dp[0] = true;

        //遍歷dp數(shù)組
        //先將wordDict放入一個unordered_set便于使用子串進(jìn)行查找
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());

        for(int i = 1; i <= s.size(); ++i){//先遍歷背包，字符串s
            for(int j = 0; j < i; ++j){//再遍歷物品
                string word = s.substr(j, i - j);//使用j不斷截取區(qū)間內(nèi)的子串
                if(wordSet.find(word) != wordSet.end() && dp[j]) dp[i] = true;
            }
        }
        return dp[s.size()];
    }
};

到了這里，關(guān)于【LeetCode動態(tài)規(guī)劃#10】完全背包問題實戰(zhàn)，其三（單詞拆分，涉及集合處理字符串）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！