139. Word Break

Loading...LeetCode

思路一：直接 DFS 枚举 wordDict 的所有permutation, 遇到等于s的就返回True

太慢， time limit exceeded

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        limit = len(s)
        def dfs(words, path):
            if path == s:
                return True
            elif len(path) < limit:
                for i in range(len(words)):
                    judge = dfs(words, path+words[i])
                    if judge:
                        return True
            else:
                return False
        return dfs(wordDict, '')

思路二：遍历 s ，在 wordDict 中搜索

节约重复计算，用 record 去记录已经算过的 sub-problem (Recursion with memoization 记忆化搜索)

class Solution(object):
    def wordBreak(self, s, wordDict)
        record = {} #记录搜索过的sub-problem
        def segement(s):
            if s in record: return record[s]
            if s in wordDict: 
                record[s] = True
                return True
            
            for i in range(1, len(s)):
            #从当前string最左开始
                r = s[:i]
                # 如果s[:i]在wordDict里面，且后面的部分也可以被分割
                # 那整个当前string就可以分割
                if r in wordDict and segement(s[i:]):
                    record[s] = True
                    return True
            
            record[s] = False
            return False
            
        return segement(s)