题目：

  1. 哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。
  2. 像句子"I reset the computer. It still didn’t boot!"已经
  3. 变成了"iresetthecomputeritstilldidntboot"。在处理标点符号和大小写之前，
  4. 你得先把它断成词语。当然了，你有一本厚厚的词典dictionary，不过，
  5. 有些词没在词典里。假设文章用sentence表示，设计一个算法，把文章断开，
  6. 要求未识别的字符最少，返回未识别的字符数。
  8. 注意：本题相对原题稍作改动，只需返回未识别的字符数
  10. 示例：
  12. 输入：
  13. dictionary = ["looked","just","like","her","brother"]
  14. sentence = "jesslookedjustliketimherbrother"
  15. 输出： 7
  16. 解释： 断句后为"jess looked just like tim her brother"，共7个未识别字符。
  18. 来源：力扣（LeetCode）
  19. 链接：https://leetcode-cn.com/problems/re-space-lcci
  20. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

答案：

时间：

30min

  1. class Solution:
  2.     def respace(self, dictionary: List[str], sentence: str) -> int:
  3.         d=set(dictionary)
  4.         n=len(sentence)
  5.         dp=[0]*(n+1)
  7.         for i in range(1,n+1):
  8.             dp[i]=dp[i-1]+1
  9.             for j in range(i+1):
  10.                 if sentence[j-1:i] in d:
  11.                     dp[i]= min(dp[j-1],dp[i])
  12.         return dp[-1]

答案二：

  1. class Solution:
  2.     def respace(self, dictionary: List[str], sentence: str) -> int:
  3.         n=len(sentence)
  4.         d=set(dictionary)
  6.         @functools.lru_cache(None)
  7.         def dfs(i):
  8.             if i==-1:return 0
  9.             res=dfs(i-1)+1
  10.             for j in range(i+1):
  11.                 if sentence[j:i+1] in d:
  12.                     res=min(res,dfs(j-1))
  13.             return res
  14.         return dfs(n-1)

答案三：Trie加速

后缀Trie

  1. from collections import defaultdict
  2. from functools import reduce
  3. TrieNode = lambda: defaultdict(TrieNode)
  4. class Trie:
  5.     def __init__(self):
  6.         self.trie = TrieNode()
  7.     def insert(self, word):
  8.         reduce(dict.__getitem__, word, self.trie)['end'] = True
  9.     def search(self, word):
  10.         return reduce(lambda d,k: d[k] if k in d else TrieNode(), word, self.trie).get('end', False)
  11.     def startsWith(self, word):
  12.         return bool(reduce(lambda d,k: d[k] if k in d else TrieNode(), word, self.trie).keys())
  14. class Solution:
  15.     def respace(self, dictionary: List[str], sentence: str) -> int:
  16.         n=len(sentence)
  17.         d=set(dictionary)
  18.         tree=Trie()
  19.         for word in d:
  20.             tree.insert(word[::-1])
  22.         dp=[0]*(n+1)
  24.         for i in range(1,n+1):
  25.             curNode = tree.trie
  26.             dp[i]=dp[i-1]+1
  27.             for j in range(i,0,-1):
  28.                 c = sentence[j-1]
  29.                 if c not in curNode:break
  30.                 if "end" in curNode[c]:
  31.                     dp[i]=min(dp[i],dp[j-1])
  32.                 curNode=curNode[c]
  33.         return dp[-1]

要点：

1. dp 定义

第 i 个字符（从1开始）中没见过的数
遍历的时候，从起点向右与当前点连线，找到即可转移。
下标很乱。
同一个位置，dp的下标要比 sentence的下标 大1

其他：

注意字典是list，要dict一下

代码报错：无