139单词拆分

发表于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        # 其实这题不用套背包问题，用简单的动态规划思路做要更加简单一些。下面是背包问题的硬套思路。
        # 将问题转为，求 一堆元素 能不能组成一个 长串。
        # 又成了背包问题，类似于求排列组合多少种方法 凑满背包的问题。
        # d[j] 是 j长度的长串 能否被凑出来，
        # 如果d[j-i]为ture，s[i:j+1] 这一截 在 词汇表中，d[j]=true ,这样递推。
        # 初始化都是 false ，d[0]= true 
        # 因为凑成的长串 和顺序有关，所以是排列，不用先固定好物品。又是不限次数是完全背包正序。
        d = [False for _ in range(len(s)+1) ]
        d[0] = True 
        wordSet = set(wordDict)
        for j in range(1,len(s)+1):   # 背包 正序
            for i in range(0,j+1):
                temp_word = s[i:j]
                if temp_word in wordSet and d[i]==True:
                    d[j] = True 
                    print(d)
        return d[len(s)]