python 英语单词拼写检查算法

本文阅读 2 分钟
首页 Python笔记 正文
  1. # 网传鹅厂面试题,英语单词拼写检查算法
  2. # 比如输入hello, 却错误的输入了hellu, 找出出错的字母
  3. # 感谢知乎知友@Lee Shellay
  4. # 对词典中的每个词, 逐刺逐字母拓展Trie, 单词完结处结点用END符号标识
  5. END = '$'
  6. def make_trie(words):
  7. trie = {}
  8. for word in words:
  9. t = trie
  10. for c in word:
  11. if c not in t:
  12. t[c] = {}
  13. t = t[c]
  14. t[END] = {}
  15. return trie
  16. # 容错查找
  17. # 实质上是对Trie的深度优先搜索,每一步加深时就消耗目标词的一个字母
  18. # 当搜索到达某个结点时,分为不消耗容错数和消耗容错数的的情形,继续搜索知道目标词为空。
  19. # 搜索过程中,用path记录搜索路径,该路径及为一个词典中存在的词,作为纠错的参考
  20. # 最终结果即为诸多搜索停止位置的结点路径的并集
  21. def check_fuzzy(trie, word, path='', tol=1): #tol为容错数
  22. if word == '':
  23. return [path] if END in trie else []
  24. else:
  25. p0 = []
  26. if word[0] in trie:
  27. p0 = check_fuzzy(trie[word[0]], word[1:], path+word[0], tol)
  28. p1 = []
  29. if tol > 0:
  30. for k in trie:
  31. if k != word[0]:
  32. p1.extend(check_fuzzy(trie[k], word[1:], path+k, tol-1))
  33. return p0 + p1
  34. # 测试代码
  35. words = ['hello', 'hela', 'dome']
  36. t = make_trie(words)
  37. print(t)
  38. print(check_fuzzy(t, 'hellu'))
  39. print(check_fuzzy(t, 'healu', tol=2))
解压密码: detechn或detechn.com

免责声明

本站所有资源出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。

本站发布资源来源于互联网,可能存在水印或者引流等信息,请用户自行鉴别,做一个有主见和判断力的用户。

本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。

Python 实现冒泡排序
« 上一篇 01-21
Python几个小的动态规划问题
下一篇 » 01-21

发表评论

惪特博客
  • 文章总数:
    18501 篇
  • 评论总数:
    53360 条
  • 标签总数:
    8881 个
  • 总浏览量:
    23333396 次
  • 最后更新:
    4天前

最多点赞

随便看看

标签TAG