精选留言(25)

• 
  Healtheon

  2019-01-07

  老师讲解得非常好，谈下个人对前缀树的了解，前缀树主要应用于以下场景： 1.预测文本输入功能：搜索引擎的输入框中输入搜索关键词的预测文本提示、IDE代码编辑器和浏览器网址中输入时的预测文本提示，借助老师讲的前两节动态规划实现预测文本的纠错功能； 2.使用前缀树结构对字符串或单词按字母顺序实现排序并进行输出的功能； 3.前缀树也可用于实现近似匹配，包括拼写检查和连字软件使用的算法； 前缀树的主要优劣对比： 1.使用前缀树可以高效地进行前缀搜索字符串和插入字符串，时间复杂度为O(length)； 2.使用前缀树可以按字母顺序轻松打印所有字符串，该功能是散列表不易实现的，但前缀树的搜索效率可能不如散列表快； 3.前缀树的缺点在于，需要大量的内存来存储字符串，对于每个节点需要太多的节点指针。倘若关注内存空间上的优化，可以考虑使用三元搜索树。三元搜索树是实现字典的首选结构，其搜索字符串的时间复杂度是O(height)；

  展开

  作者回复: 总结的很好，还有实用的场景

  共 2 条评论

  47
• 
  Healtheon

  2019-01-07

  下面是构建前缀树和查询的代码实现： package com.string.test; /** * Created by hanyonglu on 2019/1/7. */ public class TrieTest { private static final int CHARACTER_SIZE = 26; private TrieNode root; private static class TrieNode { private TrieNode[] children; private boolean isWordEnd; public TrieNode() { isWordEnd = false; children = new TrieNode[CHARACTER_SIZE]; for (int index = 0; index < CHARACTER_SIZE; index++) { children[index] = null; } } } public void insert(String key) { TrieNode newNode = root; int index; for (int i = 0; i < key.length(); i++) { index = key.charAt(i) - 'a'; if (newNode.children[index] == null) { newNode.children[index] = new TrieNode(); } newNode = newNode.children[index]; } newNode.isWordEnd = true; } public boolean search(String key) { TrieNode searchNode = root; int index; for (int i = 0; i < key.length(); i++) { index = key.charAt(i) - 'a'; if (searchNode.children[index] == null) { return false; } searchNode = searchNode.children[index]; } return (searchNode != null && searchNode.isWordEnd); } public static void main(String args[]) { String[] keys = {"my", "name", "is", "hanyonglu", "the", "son", "handongyang", "home", "near", "not", "their"}; TrieTest trieTest = new TrieTest(); trieTest.root = new TrieNode(); for (int index = 0; index < keys.length ; index++) { trieTest.insert(keys[index]); } System.out.println("home result : " + trieTest.search("home")); System.out.println("their result : " + trieTest.search("their")); System.out.println("t result : " + trieTest.search("t")); } }

  展开

  作者回复: 实现很简洁👍

  

  25
• 
  cwtxz

  2019-12-29

  通过这段时间的学习，我明白了，数学提供的是解决问题的思路，而编程是实现这个思路的工具和手段。编程的语言多种多样，针对同一个问题，可以采用各种各样的编程语言来实现，也可以采用各种各样的方法和思路去解决，但是有一点是相同的：没有思想的上层指导，下层的技术实现就是无根浮萍，指望脱离了思想的技术来解决问题，完全是痴心妄想。数学是思想，以思想之道驾驭技术之术，才能无往不利，所向披靡。加油!!!继续钻研《程序员的数学基础课》。

  展开

  共 1 条评论

  10
• 
  Being

  2019-01-07

  关于思考题的一点想法：其实可以将单词以及字母抽象出来，利用组合模式，形成树形关系，实现递归调用。

  作者回复: 如果使用前缀树，对给定的一些单词进行处理，就无需排列组合了

  

  5
• 
  罗耀龙@坐忘

  2020-04-03

  茶艺师学编程 这节课我要记住的概念 前缀树（字典树） 图/有向图＆混合图/入度＆出度/深度优先搜索＆深度有限遍历 可以结合我们（小学）学习使用字典的经历来理解前缀树。先从第一个字母开始，一个字母一个字母地往下找…… 人们常说的“要把学到的知识搭建起来”，前缀树就是很好的一种结构：这个知识点，它的源头是什么（找父节点）、谁在支持这个点谁在反对这个点?（找后辈节点）……

  展开

  共 1 条评论

  5
• 
  梦倚栏杆

  2019-03-26

  对于二叉树而言，深度优先遍历是不是就是二叉树的先序遍历啊

  作者回复: 确切的说，先序、中序和后序是深度优先遍历的三种方式

  

  3
• 
  建强

  2019-12-07

  用Python写了一个简单的程序： # 前缀树构造与查询 # 前缀树节点 class PrefixNode: def __init__(self, letter): self.letter = letter # 每个节点中存储一个单词的字母 self.childnode = {} # 子节点用字典存储 self.isend = False # isend表示单词是否结束 def addchild(self, child): self.childnode[child.letter] = child # 寻找字母为letter的子节点 def findchild(self, letter): return self.childnode.get(letter) # 前缀树 class PrefixTree: def __init__(self): self.root = PrefixNode('#') # 用#号代表根节点 # 向字典树中加入一个单词 def addWord(self, word): p = self.root for w in word: childnode = p.findchild(w) if childnode is None: # 前缀树中没有找到对应的字母，则重新构造一个新的子节点 childnode = PrefixNode(w) p.addchild(childnode) p = childnode p.isend = True # 在字典树中查找一个单词 def searchWord(self, word): p = self.root for w in word: childnode = p.findchild(w) if childnode is None: # 前缀树中没有找到对应的字母，则直接返回False return False p = childnode return p.isend # 主程序 def main(): # 构造字典树 dict_tree = PrefixTree() # 向字典树中加入一些单词 for word in ['beautiful','student','computer','desk','table','design','book','bookshelf']: dict_tree.addWord(word) print('prefix tree is maded') # 在字典树中查找单词 for word in ['beau', 'book','student', 'conputer', 'bookshelf', 'desks']: if dict_tree.searchWord(word): print('"{}" was founded.'.format(word)) else: print('"{}" was not founded.'.format(word)) if __name__ == '__main__': main()

  展开

  

  3
• 
  NullPointer

  2019-01-09

  老师讲的很好，非常容易理解。😁这次就不做作业了

  

  2
• 
  Cutler

  2020-11-07

  正好最近刷到了leetcode上一道关于trie树的题 ## Algorithm ### 1. 题目 ``` 208. 实现 Trie (前缀树) ``` ### 2. 题目描述 ``` 实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。 示例: Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // 返回 true trie.search("app"); // 返回 false trie.startsWith("app"); // 返回 true trie.insert("app"); trie.search("app"); // 返回 true 说明: 你可以假设所有的输入都是由小写字母 a-z 构成的。 保证所有输入均为非空字符串。 ``` ### 3. 解答： ```golang type Trie struct { data byte child []*Trie isEnd bool } /** Initialize your data structure here. */ func Constructor() Trie { return Trie{ data: '/', child: make([]*Trie, 26, 26), isEnd: false, } } func newTrie(data byte) *Trie { return &Trie{ data: data, child: make([]*Trie, 26, 26), } } /** Inserts a word into the trie. */ func (t *Trie) Insert(word string) { p := t for _, c := range word { index := c - 'a' if p.child[index] == nil { p.child[index] = newTrie(byte(c)) } p = p.child[index] } p.isEnd = true } /** Returns if the word is in the trie. */ func (t *Trie) Search(word string) bool { p := t for _, c := range word { index := c - 'a' if p.child[index] == nil { return false } p = p.child[index] } if !p.isEnd { return false } else { return true } } /** Returns if there is any word in the trie that starts with the given prefix. */ func (t *Trie) StartsWith(prefix string) bool { p := t for _, c := range prefix { index := c - 'a' if p.child[index] == nil { return false } p = p.child[index] } return true } ``` ### 4. 说明 1. 定义Trie的结构中包含的child 2. child数组用26个英文字符表示，用字符减去`a`就得到数组中的索引

  展开

  作者回复: Leetcode是不错的编程训练资源

  

  1
• 
  Paul Shan

  2019-08-22

  树是一种递归结构，由根节点和若干子树构成。在建树和查找上也会充分利用这种递归结构。

  

  1
• 
  是我

  2019-05-16

  觉得二叉树跟正则表达式好像

  作者回复: 具体是哪种正则表达式？

  共 2 条评论

  1
• 
  qinggeouye

  2019-02-20

  查找到一个 python 版本，分别用迭代循环和递归的方法，实现在树中添加和查找单词。动手实现了一遍：～ https://github.com/qinggeouye/GeekTime/blob/master/MathematicProgrammer/11_deepFirstSearch/lesson11_1.py

  

  1
• 
  WL

  2019-01-07

  不错不错, 又把大学忘掉的知识复习了一遍

  

  1
• 
  克己求生

  2022-04-05

  class TrieNode: def __init__(self, letter): self.letter = letter self.children = {} self.pre_node = None def insert(self, node): node.pre_node = self self.children[node.letter] = node def insert(word, parent_node): for l in word: if l not in parent_node.children: node = TrieNode(l) parent_node.insert(node) parent_node = node else: parent_node = parent_node.children[l] def search(word, parent_node): for l in word: if l in parent_node.children: parent_node = parent_node.children[l] if l == word[-1]: print("Found word: {}".format(word)) return 0 else: print("Not found!") return -1

  展开

  

  
• 
  崔晓乐

  2021-09-14

  这里的简单回路，其实就是指，除了第一个结点和最后一个结点相同外，其余结点不重复出现的回路？ 这句话怎么理解呢？ 其余结点不重复出现的回路？

  作者回复: 就是说只有第一个结点和最后一个结点重复出现。而其他的所有结点都只出现一次

  

  
• 
  张祈璟

  2021-06-10

  把词都放在个数据库里，查询的时候用like，与把词放树里的效率哪个高？实现起来哪个简单？

  作者回复: 数据库的like应该是模糊匹配，通常情况下没有字典树精确匹配的效率高

  

  
• 
  北极的大企鹅

  2021-04-12

  讲得非常好

  作者回复: 很高兴对你有价值

  

  
• 
  aoe

  2019-12-02

  这次通俗易懂，感谢老师

  作者回复: 很高兴对你有价值

  

  
• 
  Eleven

  2019-11-25

  老师，这篇概念有点多啊，文章中说的有向边该怎么理解呢？

  作者回复: 有向边是指从某个节点到另一个节点存在方向，顺向可以走通，逆向就不行

  

  
• 
  花指令

  2019-11-04

  发现大家用循环遍历确定节点，既然是字母，大小写最多就52个，那应该用ascii做二分搜索更快，分布均匀的话还可以直接用数组下标

  作者回复: 如果只限定在英文，这是个好方法👍

  

  