Leetcode題解 WordBreak

2021-03-02 程式設計師大白

點擊上方「程式設計師大白」，選擇「星標」公眾號

重磅乾貨，第一時間送達

題意

題目：單詞斷開  給定一個非空的字符串s和一個字典wordDict，字典中包含許多非空的單詞，確定字符串s是否可以分割成通過字典中的一個或多個單詞組成的空格隔開的序列.假定字典中不包含重複的單詞.  舉個例子，給定  

s = "leetcode",
dict = ["leet", "code"].
上述將返回true，因為"leetcode"可以分割成"leet code".  更新:  參數wordDict已經從原來的字符串的集合更新為字符串的數組，請重新加載代碼的定義以獲取最新改變.  
題解
算法及複雜度（6 ms）  本問題是確定一個字符串是否能分割成多個單詞，這些單詞都在字典中出現.  由於本題每個組成成分都是單詞，也就是每次在原有字符串的返回true的基礎上增加一個字典中的單詞來組成新的能夠返回true的字符串.發現這是一種全局同一限制性的求解問題，限制條件是每次字符串增加的都是一個存在於字典中的單詞.舉個例子說明一下:  比如字符串是"leetcodeisnice"，字典是["leet", "code", "is", "nice"].要想"leetcodeisnice"返回true，需要從後向前尋找一個單詞（"nice"），這個單詞在字典中，並且字符串的之前的部分（"leetcodeis"）本身是返回true的.全局同一限制性的求解問題可以通過動態規划進行求解.  由此，可以得到狀態轉移過程，用dp[i]表示以字符串s中以第i個字符結尾的字符串(0, i - 1)返回true或者false.那麼dp[i]可以通過判斷所有的j截取s得到子串s(j, i - 1)其中0 < j < j - 1存在於字典中，且dp[j - 1]已經求得為true，來確定dp[i]為true，如果不存在滿足上述條件的j，則返回false.  時間複雜度: O(n ^ 2 * len(wordDict)). n表示字符串s的長度，由於需要對每個位置進行求解，並且對於每個位置，需要求解之前的狀態來確定現在的狀態，這樣的複雜度最壞為O(n ^ 2)，而每次確定過程中還需要在字典中進行搜索子串是否存在，需要再乘以len(wordDict).  代碼參見本文件夾下solution.cpp  
算法正確性
舉個例子  
// 輸入數據 s = "leetcode", wordDict = ["leet","code"]

// 初始化 dp[0] = true

// i = 1，"l"不存在於字典中
dp[1] = false
// i = 2，"e"不存在於字典中，"le"不存在於字典中
dp[2] = false
// i = 3, "e"不存在於字典中，"ee"不存在於字典中，"lee"不存在於字典中，
dp[3] = false
// i = 4, "t"不存在於字典中，"et"不存在於字典中，"eet"不存在於字典中，"leet"存在於字典中，且dp[i - len("leet")] = true
dp[4] = true

// i = 5，"c"不存在於字典中，"tc"不存在於字典中，"etc"不存在於字典中，"eetc"不存在於字典中，"leetc"不存在於字典中，
dp[5] = false
// i = 6，"o"不存在於字典中，"co"不存在於字典中，"tco"不存在於字典中，"etco"不存在於字典中，"eetco"不存在於字典中，"leetco"不存在於字典中，
dp[6] = false
// i = 7，"d"不存在於字典中， "od"不存在於字典中，"cod"不存在於字典中，"tcod"不存在於字典中，"etcod"不存在於字典中，"eetcod"不存在於字典中，"leetcod"不存在於字典中，
dp[7] = false
// i = 8，"e"不存在於字典中，"de"不存在於字典中, "ode"不存在於字典中，"code"存在於字典中，且dp[i - len("code")] = true
dp[8] = true

// 返回結果
return true
注意： 為了減少一下計算量，代碼中把dp[j] == true的判斷放在了查找子串是否屬於字典判斷的前面.  
CPP代碼
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        
        int len = s.length();
        vector<bool>dp(len + 1);
        
        dp[0] = true;
        for(int i = 1; i <= len; i ++) {
            for(int j = i - 1; j >= 0; j --) {
                if(dp[j] == true && (find(wordDict.begin(), wordDict.end(), s.substr(j, i-j)) != wordDict.end())) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[len];
    }
};
重磅！程式設計師大白交流群-學術微信交流群已成立
額外贈送福利資源！邱錫鵬深度學習與神經網絡，pytorch官方中文教程，利用Python進行數據分析，機器學習學習筆記，pandas官方文檔中文版，effective java（中文版）等20項福利資源
獲取方式：進入群後點開群公告即可領取下載連結
注意：請大家添加時修改備註為 [學校/公司 + 姓名 + 方向]
例如 —— 哈工大+張三+對話系統。
號主，微商請自覺繞道。謝謝！
推薦閱讀
Leetcode題解 SimplifyPath
Leetcode題解 InsertInterval
Leetcode題解 MergeIntervals
Leetcode題解 JumpGame
Leetcode題解 N-Queens
Leetcode題解 Trapping Rain Water
關於程式設計師大白
程式設計師大白是一群哈工大，東北大學，西湖大學和上海交通大學的碩士博士運營維護的號，大家樂於分享高質量文章，喜歡總結知識，歡迎關注[程式設計師大白]，大家一起學習進步！

相關焦點

  • Leetcode題解 WordBreakII
    解題思路這題和Leetcode 132很像，同樣是切分，同樣是切分出來的要滿足一定條件，不同的是這題要輸出所有的可能性。> word;        for(auto str:wordDict)            word.insert(str);        int n=s.size();        vector<vector<int>> dp(n+1);        dp[0].push_back(0);
  • [每日一題]140. Word Break II
    本題難度：Hard做題日期：2017年3月26日本題地址:  https://leetcode.com/problems
  • Leetcode題解 Word_Search
    解題思路採用搜索，枚舉board中的一條路徑，並且在枚舉的過程中一邊檢查是否能夠匹配上word，如果順利的匹配完了所有word的字符，就說明找到了；如果枚舉結束之後仍然沒有找到，就說明不存在。一定要注意能剪枝的地方要剪枝，如搜索到了結果，就直接跳出來，不再進行搜索了.搜索過程中，進行相應位置匹配的時候，進入下一步搜索，如果長度與word長度一樣說明已經在矩陣中已經找到了一個單詞。
  • [LeetCode] 916. Word Subsets 單詞子集合
    Each word is a string of lowercase letters.Now, say that word b is a subset of word a if every letter in b occurs in a, including multiplicity.
  • ​LeetCode刷題實戰139:單詞拆分
    所以，為了提高大家的算法能力，這個公眾號後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！今天和大家聊的問題叫做 單詞拆分，我們先來看題面：https://leetcode-cn.com/problems/word-break/Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be
  • Leetcode刷題-動態規劃
    本文對leetcode上部分動態規劃問題進行分析並用python實現5. 最長回文子串 題目描述給定一個字符串 s，找到 s 中最長的回文子串。你可以假設 s 的最大長度為 1000。整體代碼結構也是與第五題的動態規劃代碼類似。
  • Leetcode題解 Edit Distance
    下面舉一個簡單例子走一遍算法幫助理解：word1=」ad」，word2=」abc」。1，j=2，word1[0]!=word2[1]，dp1=min(dp0+1,dp1+1,dp0+1)=2；i=1，j=3，word1[0]!=word2[2]，dp1=min(dp0+1,dp1+1,dp0+1)=3；i=2，j=1，word1[1]!
  • Leetcode刷題-字符串
    字符串其實可以看成是字符組成的數組，在leetcode中一般會有以下幾種題型：不同的字符串題方法也不同，下面具體介紹了5個涉及字符串題的解題思路和python解決方案尤其最後一題尋找最長回文子串問題中，給出了全新的動態規劃思路
  • 開源項目 | 用Python美化LeetCode倉庫
    GitHub：https://github.com/KivenCklLeetCode簡介leetcode是一個美國的在線編程網站，它收集了各大公司的經典算法面試題，用戶可以選擇不同的語言進行代碼的在線編寫、編譯和調試。簡單來說，它就是程式設計師的刷題神器。
  • LeetCode-4-動態規劃
    示例 2：輸入: "cbbd"輸出: "bb"題解一|暴力破解：    很明顯，暴力法將選出所有子字符串可能的開始和結束位置，並檢驗它是不是回文。https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-cshi-xian-si-chong-jie-fa-bao-li-f/題解一：遍歷整個數組，在數組的每一個位置時，求出一個全局最大值L，代表以當前位置為結尾的最大字串，而G是當前位置的L和上一個位置L相比較後，
  • [每日一題]139. Word Break
    For example, givens = "leetcode",dict = ["leet", "code"].Return true because "leetcode" can be segmented as "leet code".簡單的解釋：就是要給定一個字符串和一個字典，判斷該字符串中等詞是否由字典中的詞組成。
  • ​LeetCode刷題實戰79:單詞搜索
    所以，為了提高大家的算法能力，這個公眾號後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！今天和大家聊的問題叫做 單詞搜索，我們先來看題面：https://leetcode-cn.com/problems/word-search/Given a 2D board and a word, find if the word exists in the grid.
  • ​LeetCode刷題實戰140:單詞拆分 II
    所以，為了提高大家的算法能力，這個公眾號後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！今天和大家聊的問題叫做 單詞拆分 II，我們先來看題面：https://leetcode-cn.com/problems/word-break-ii/Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s
  • 回溯法|一文解決四道 Leetcode「組合總和」題
    解集不能包含重複的組合。解集不能包含重複的組合。 組合總和」 和 「leetcode-40.1.2 題目分析當我們遇到：「可行解是什麼、可行解有多少個」這類問題時，最樸素的想法就是「枚舉」，枚舉出所有可能的結果，並在枚舉的過程中不斷刪除不符合條件的解。
  • Go 實現 LeetCode 全集
    Water - https://leetcode.com/problems/container-with-most-water/Binary[X] Sum of Two Integers - https://leetcode.com/problems/sum-of-two-integers/[X] Number of 1 Bits - https://leetcode.com
  • LeetCode-14. Longest Common Prefix | 最長公共前綴
    題解這道題目的簡單描述就是找一堆字符串的相同前綴，比如flower、flow、flight，發現每個字符串都有前綴fl，於是就將fl返回即可，本題就是要實現這樣一個在字符串數組中找最長前綴的函數。  = v[i] { //做判斷，如果不相等 break //直接結束循環 } } res = res[:i] if res == "" { return res //返回空 } } return res}另一種相似解法，會用到strings.Index
  • leetcode之整理字符串
    序本文主要記錄一下leetcode之整理字符串題目給你一個由大小寫英文字母組成的字符串 s 。
  • 第五題:最長回文子串【leetcode】
    難度：中等連結：https://leetcode-cn.com/problems/longest-palindromic-substring/方法一、暴力破解法，第一層循環從字符串開頭開始遍歷，第二層字符串從結尾開始遍歷，當找到與開頭的字符一樣的時候，對比它們之間的字符串，將區間字符串逐一對比，如果是回文且比臨時最大回文字符串的長度對比，如果大於重新賦值最大回文字符串，如果小於跳過
  • 最長公共前綴 | Leetcode題解
    ==comPre[j])break    }    if(j===0)return ''    comPre=comPre.substring(0,j)  }  return comPre};/** * @param {string[]} strs * @return
  • [LeetCode] 953. Verifying an Alien Dictionary 驗證外星文字典
    若對應位上的字母相同，則直接跳過；若前面的字母順序靠後，則直接返回 false，否則 break 掉（注意這裡不能直接返回 true 的原因是後面有可能還會出現不合題目要求的情況）。之後還要驗證前面提到的一種情況，就是當較短的單詞是較長單詞的子串時，而且後面的單詞較短時，也需要返回 false。