專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服
專欄：50多種經(jīng)典圖論算法全部掌握
最近在網(wǎng)上看到一個(gè)新聞，一位游戲大廠員工的女友，發(fā)文炫耀自己未婚夫2024年薪突破300萬，前不久過生日直接給她轉(zhuǎn)了4萬零花錢，還在廣州買了一套大平層，本打算在今年十一準(zhǔn)備結(jié)婚的。結(jié)果被同一家公司員工發(fā)現(xiàn)，并舉報(bào)，最后被裁。
實(shí)際上這種"坑夫式炫富"并非個(gè)例。2022年中金交易員妻子曬出的8.25萬月薪單，直接引發(fā)金融圈薪酬整頓風(fēng)暴，全行業(yè)人均薪資縮水20%。雖然說互聯(lián)網(wǎng)公司薪資都是保密的，有的甚至還會(huì)簽訂保密協(xié)議，薪資不能向外人透露，但也不至于被裁吧，我想應(yīng)該還有其他原因。
--------------下面是今天的算法題--------------
來看下今天的算法題，這題是LeetCode的第139：單詞拆分。
問題描述
來源：LeetCode第139題
難度：中等
給你一個(gè)字符串 s 和一個(gè)字符串列表 wordDict 作為字典。如果可以利用字典中出現(xiàn)的一個(gè)或多個(gè)單詞拼接出 s 則返回 true。
注意：不要求字典中出現(xiàn)的單詞全部都使用，并且字典中的單詞可以重復(fù)使用。
示例1：
輸入: s = "leetcode", wordDict = ["leet", "code"] 輸出: true 解釋: 返回 true 因?yàn)?"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 ，實(shí)際上就是把字符串 s 拆分成一些子串，并且判斷這些子串是否都存在字典wordDict中。這題解決方式比較多，有動(dòng)態(tài)規(guī)劃，還有BFS和DFS，我們先來看動(dòng)態(tài)規(guī)劃怎么解決。
定義dp[i]表示字符串的前 i 個(gè)字符經(jīng)過拆分是否都存在于字典wordDict中。如果求dp[i]，需要往前截取 k 個(gè)字符，判斷子串[i-k+1，i]是否存在于字典wordDict中，并且前面子串[0，i-k]拆分的子串也是否都存在于wordDict中，如果都存在，說明可以拆分。
如下圖所示，如果我們要判斷字符串“catsan”是否可以正常拆分，我們先截取前 6 個(gè)字符，判斷它們是否存在于字典中，如果不存在，就截取 5 個(gè)，4個(gè)……，如果存在，還需要判斷剩下的字符是否可以正常拆分。
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]才會(huì)返回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]才會(huì)返回true。 if (dp[j] && wordSet.find(s.substr(j, i - j)) != wordSet.end()) { dp[i] = true;// 只要有一種方式能夠拆分成功，后面就不要嘗試拆分了。 break; } } } return dp[len]; }
筆者簡介
博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個(gè)算法網(wǎng)站中累計(jì)做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨(dú)特的解題思路和解題技巧，喜歡的可以給個(gè)關(guān)注，也可以 下載我整理的1000多頁的PDF算法文檔 。
熱門跟貼