古人有云：“一杯茶，一包烟，一个bug调一天。” 今天我是切身体会到代码出问题，还是在逻辑语法都没问题的情况下的心塞。后来才发现是题目提供的方法名我少写了一个"s"，就是下面startswith的方法名中的s。就这一个小点，搞了3个多小时！！！！ 废话不多说，我们来看看什么是前缀树：又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。 搜索字典项目的方法为： (1) 从根结点开始一次搜索； (2) 取得要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索； (3) 在相应的子树上，取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。 (4) 迭代过程…… (5) 在某个结点处，关键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找。 其他操作类似处理。 具体的应用：串的快速检索、“串”排序、最长公共前缀 介绍完定义之后，我们来从力扣上一道题入手来编写Trie树。 leetcode208. 实现 Trie (前缀树) 链接：https://leetcode-cn.com/problems/implement-trie-prefix-tree/ 难度：中等 题目： 实现一个 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 方法一： 第一步我们先要构建树的结点:由题目要求可以知道
class TrieNode { boolean isleaf; Map<Character,TrieNode> next;//用来存，下一个结点的信息，K是存储字符，Value存储结点 public TrieNode(){ next=new HashMap<Character,TrieNode>(); } }第二步构建Trie树,并实现search、insert、startswith方法
class Trie{ private TrieNode root;//定义根节点 public Trie(){ root = new TrieNode(); } //方法：插入方法 public void insert(String word){ if(word == null || word.length() == 0){ return ; } TrieNode node = root; int len=word.length(); for(int i=0;i<len;i++){ Character c = word.charAt(i); TrieNode tempNode = node.next.get(c); if(tempNode == null){ tempNode = new TrieNode(); node.next.put(c,tempNode); } node=tempNode; } node.isleaf = true; } //search方法 public boolean search(String word){ if(word == null || word.length() == 0){ return false; } TrieNode node =root; int len=word.length(); for(int i=0;i<len;i++){ Character c = word.charAt(i); TrieNode tempNode = node.next.get(c); if(tempNode == null){ return false; } node = tempNode; } return node.isleaf; } //返回trie中是否有给定前缀开头的单词 public boolean startsWith(String prefix){ if(prefix == null || prefix.length() == 0) return false; TrieNode node = root; int len=prefix.length(); for(int i=0;i<len;i++){ TrieNode tempNode = node.next.get(prefix.charAt(i)); if(tempNode == null){ return false; } node=tempNode; } return true;//不需要判断是否是叶结点 } }方法二： 构建结点：是用数组，其实在结点构造这块，定义的方法是模拟map
class TrieNode{ private TrieNode[] links; private final int R=26; private boolean isEnd; public TrieNode(){ links=new TrieNode[][R]; } public boolean containsKey(char ch){ return links[ch-'a'] != null; } public TrieNode get(char ch){ return links[ch-'a']; } public void put(char ch,TrieNode node){ links[ch-'a']=node; } public void setEnd(){ isEnd=true; } public boolean isEnd(){ return isEnd; } }构建trie：
public class Trie { private TrieNode root; public Trie(){ root = new TrieNode(); } //inset public void insert(String word){ if(word == null || word.length() == 0) return ; TrieNode node =root; for(int i=0;i<word.length();i++){ char c = word.charAt(i); if(!node.containsKey(c)){ node.put(c,new TrieNode()); } node = node.get(c);//node指向下一个结点 } node.setEnd(); } //searchPrefix public TrieNode searchPrefix(String word){ if(word == null || word.length() == 0) return false; TrieNode node=root; for(int i=0;i<word.length();i++){ char c = word.charAt(i); if(node.containsKey(c)){ node=node.get(c); }else{ return null; } } return node; } //search public boolean search(String word){ TrieNode node = searchPrefix(word); return node != null && node.isEnd(); } }希望世界少一点bug，多一点爱！
