【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 整体就满足条件。

【leetcode】Word Break(python)

class Solution:
    # @param s, a string
    # @param dict, a set of string
    # @return a boolean
    def wordBreak(self, s, dict):
        if len( s ) == 0 or len(dict) == 0:
            return False
        #初始长度为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)
                    break
        return dp[-1] == len( s )







【leetcode】Word Break(python),布布扣,bubuko.com

【leetcode】Word Break(python)

上一篇:javascript入门视频第一天 小案例制作 零基础开始学习javascript


下一篇:javascript里的封装