專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

最近在網上看到一個新聞，一位游戲大廠員工的女友，發文炫耀自己未婚夫2024年薪突破300萬，前不久過生日直接給她轉了4萬零花錢，還在廣州買了一套大平層，本打算在今年十一準備結婚的。結果被同一家公司員工發現，并舉報，最后被裁。

實際上這種"坑夫式炫富"并非個例。2022年中金交易員妻子曬出的8.25萬月薪單，直接引發金融圈薪酬整頓風暴，全行業人均薪資縮水20%。雖然說互聯網公司薪資都是保密的，有的甚至還會簽訂保密協議，薪資不能向外人透露，但也不至于被裁吧，我想應該還有其他原因。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第139：單詞拆分。

問題描述

來源：LeetCode第139題

難度：中等

給你一個字符串 s 和一個字符串列表 wordDict 作為字典。如果可以利用字典中出現的一個或多個單詞拼接出 s 則返回 true。

注意：不要求字典中出現的單詞全部都使用，并且字典中的單詞可以重復使用。

示例1：

輸入: s = "leetcode", wordDict = ["leet", "code"] 輸出: true 解釋: 返回 true 因為 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例2：

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

• 1 <= s.length <= 300

• 1 <= wordDict.length <= 1000

• 1 <= wordDict[i].length <= 20

• s 和 wordDict[i] 僅由小寫英文字母組成

• wordDict 中的所有字符串 互不相同

問題分析

這題判斷能否用字典中的字符串拼接成字符串 s ，實際上就是把字符串 s 拆分成一些子串，并且判斷這些子串是否都存在字典wordDict中。這題解決方式比較多，有動態規劃，還有BFS和DFS，我們先來看動態規劃怎么解決。

定義dp[i]表示字符串的前 i 個字符經過拆分是否都存在于字典wordDict中。如果求dp[i]，需要往前截取 k 個字符，判斷子串[i-k+1，i]是否存在于字典wordDict中，并且前面子串[0，i-k]拆分的子串也是否都存在于wordDict中，如果都存在，說明可以拆分。

如下圖所示，如果我們要判斷字符串“catsan”是否可以正常拆分，我們先截取前 6 個字符，判斷它們是否存在于字典中，如果不存在，就截取 5 個，4個……，如果存在，還需要判斷剩下的字符是否可以正常拆分。

JAVA：

public boolean wordBreak(String s, List wordDict)  {     int len = s.length();     boolean[] dp = newboolean[len + 1];     dp[0] = true;// 空字符串，不需要字典中的字符串。     for (int i = 1; i <= len; i++) {         for (int j = 0; j < i; j++) {             // 把字符串分割為s[0,j-1]和s[j,i]兩部分，             // 這兩部分必須都存在于字典中dp[i]才會返回true。             dp[i] = dp[j] && wordDict.contains(s.substring(j, i));             if (dp[i])// 只要有一種方式能夠拆分成功，后面就不要嘗試拆分了。                 break;         }     }     return dp[len]; }

C++：

public:     bool wordBreak(string s, vector

 &wordDict) {         size_t len = s.size();         vector

  dp(len + 1, false);         unordered_set

  wordSet(wordDict.begin(), wordDict.end());         dp[0] = true;// 空字符串，不需要字典中的字符串。         for (int i = 1; i <= len; i++) {             for (int j = 0; j < i; j++) {                 // 把字符串分割為s[0,j-1]和s[j,i]兩部分，                 // 這兩部分必須都存在于字典中dp[i]才會返回true。                 if (dp[j] && wordSet.find(s.substr(j, i - j)) != wordSet.end()) {                     dp[i] = true;// 只要有一種方式能夠拆分成功，后面就不要嘗試拆分了。                     break;                 }             }         }         return dp[len];     }

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。