【leetcode】Word Break（python）

思路是这种。我们从第一个字符開始向后依次找，直到找到一个断句的地方，使得当前获得的子串在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）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。