时间复杂度(O(n*m))
思想：动态规划
class Solution:def wordBreak(self, s: str, wordDict: [str]) -> bool:if len(s) == 0: return Trueif len(wordDict) == 0: return Falsewords = set(wordDict)max_len_word = max([len(w) for w in words])res = [False] * len(s)for i in range(len(s)):if i > 0 and res[i - 1] != True: continuefor j in range(i + 1, min(len(s) + 1, i + max_len_word + 1)):if s[i: j] in words:res[j - 1] = Truereturn res[-1]思想：前缀字典+动态规划（理论上，当数据量比较大的时候，效率更好）
class Solution:def wordBreak(self, s: str, wordDict: [str]) -> bool:if len(s) == 0: return Truepre_words = {}for word in wordDict:#构建前缀字典if word not in pre_words: pre_words[word] = [0, 1]else: pre_words[word] = [pre_words[word][0], 1]for j in range(1, len(word)):if word[:j] not in pre_words: pre_words[word[:j]] = [1, 0]else: pre_words[word[:j]] = [1, pre_words[word[:j]][1]]res = [False] * len(s)for i in range(len(s)):if i > 0 and res[i - 1] != True: continuefor j in range(i + 1, len(s) + 1):if s[i:j] not in pre_words: breakpre, e = pre_words[s[i:j]]if e == 1: res[j - 1] = Trueif pre == 0: breakreturn res[-1]