思路是這種。我們從第一個字符開始向后依次找，直到找到一個斷句的地方，使得當前獲得的子串在dict中，若找到最后都沒找到。那么就是False了。

在找到第一個后，接下來找下一個斷句處，當然是從第一個斷句處的下一個字符開始找連續的子串，可是這時與第一個就稍有不同。比方說word=‘ab’， dict={ 'a', ab', ...},在找到a后，接下來處理的是b。我們發現b不在dict中，可是我們發現b能夠和a結合，形成ab，而ab在dict中。所以這里的每一個子串就能夠有三種選擇。要么自己單獨作為個體到dict中找，要么就跟前面的結合起來進行找。要么就是等，等后面的新的字符。構成更長的子串。

可是還有問題，上面我們說的是跟前面的結合起來找。那么這個前面是個什么定義？開頭？開頭后的第一個？ 第二個？所以我們要記錄一些信息。來表示前面的子串，是從哪里斷開，從而滿足條件的。那么我們就能夠依次與離當前子串近的部分進行結合。比方：word = ’aab‘， dict = { a, aab }。處理a時。是滿足的，下一個a。也是滿足的，處理 b 時，b不在dict中，那么就與前面的a結合， 形成 ab，發現不在dict 中，那么繼續與前面的結合，形成 aab，發如今dict 中，那么 word 總體就滿足條件。

class Solution:# @param s, a string# @param dict, a set of string# @return a booleandef wordBreak(self, s, dict):if len( s ) == 0 or len(dict) == 0:return False#初始長度為0，表示的是之前的元素已經搞定，能夠從0開始繼續向后dp = [ 0 ]# s串的長度，[1， len ( s )]。我們挨個去搞定興許的斷句for i in range(1, len( s ) + 1):#前面全部的合法的斷句處，也就是全部的合法的起始點，由于若前面的都沒搞定。不能夠繼續后面的for j in xrange( len( dp ) - 1, -1, -1):substr = s[dp[j] : i]if substr in dict:dp.append(i)breakreturn dp[-1] == len( s )

轉載于:https://www.cnblogs.com/blfbuaa/p/7201900.html

總結

以上是生活随笔為你收集整理的【leetcode】Word Break（python）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。