140. Word Break II

Loading...LeetCode

本质就是往s里面插空格，确认valid就是检查跟上一个空格间的string是否是dict中的词，合格的话就记录一下状态，然后继续往下试。这个方法很容易想到backtracking，每个位置都需要判断插空格or不插，时间复杂度在O(2**n)，提交TLE了。

既然TLE就检查哪里有重复运算，发现对于不同的前部分分割，存在可能相同的后部分分割，或者说，对于同样的后部分分割，存在可能相同的前部分分割。或者更加 generally，对于某个重复出现的pattern，其分割方式可以是一样的，那就不需要重复运算。

比如 example 2 里的 "pineapple" 这个pattern：

Output:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]

如果用hashmap来记录一下某string的有效分割结果，就可以避免重复运算。这样就是把 backtracking变成了一个记忆化搜索（or you can call it DP whatever）。

backtracking (TLE)

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        self.result = set()
        self.backtracking(wordDict, -1, s)
        return self.result
        
    def backtracking(self, wordDict, last, path):
        for idx in range(last+1, len(path)):
            if path[last+1:idx+1] in wordDict:
                if idx+1 == len(path):
                    self.result.add(path)
                else:
                    self.backtracking(wordDict, idx+1, path[:idx+1]+' '+path[idx+1:])

memorization

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        self.memo = dict()
        
        def backtracking(string):
            # 搜到尾巴了，添加一个空字符串。直接返回空数组的话，会导致无法iterate，结果不被记录。
            if not string: return [""]
            if string in self.memo: return self.memo[string]
            
            stage = []
            for i in range(len(string)):
                w = string[:i+1]
                # 如果 w 在字典中，则去掉 w 继续探索
                if w in wordDict:
                    remain = backtracking(string[i+1:])
                    # 记录结果
                    # strip用来去掉p是空值时尾巴的空格
                    stage.extend([(w+" "+p).strip() for p in remain])
            self.memo[string] = stage
            return stage
        
        return backtracking(s)