【Leetcode】139. Word Break解题报告

求wordDict中的单词是否能拼接成s,可以重复。

方法1

使用深度优先搜索，如果s以wordDict中的某个单词word开头，那么就将S去掉word的部分继续进行深搜，知道剩下的部分为空位置，说明能找到拼接的方法。
超时代码

class Solution:
    def wordBreak(self, s, wordDict):
        self.res = False
        self.DFS(wordDict, s)
        return self.res


    def DFS(self, wordList, rest_string):
        if self.res == True:
            return
        if rest_string == "":
            self.res = True
            return
        for word in wordList:
            if rest_string[:len(word)] == word:
                self.DFS(wordList, rest_string[len(word):])

方法2 DP

这是一道经典的DP问题，我们用dp[i]表示字符串s[:i] 是否可悲拼接而成，那么dp[i如何求呢，我们遍历wordDict,如果对于每一个word,s[:i-len(word)]可以被拼接而成，那么s[:i]可由s[:i-len(word)]和word拼接而成。设置dp[0] 为True即可解决问题。

class Solution:
    def wordBreak(self, s, wordDict):
        dp = [False] * (len(s) +1 )
        dp[0] =True
        for i in range(1,len(dp)):
            for word in wordDict:
                if i - len(word) >= 0 :
                    dp[i] = dp[i-len(word)] or dp[i] if s[i-len(word):i] ==  word else dp[i]
        return dp[-1]