实现前缀树

Trie（发音类似 “try”）或者说 前缀树
是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

力扣208 https://leetcode-cn.com/problems/implement-trie-prefix-tree/

许多搜索引擎都是使用这种方式实现的

总的来说是，root节点不存值，其他每个节点中都存储单一字符。

这里我使用HashMap实现，因为这种实现方法添加节点更灵活。

class TrieNode {public Character vaCharacter;public Map children = new HashMap<>();private boolean isEnd;public TrieNode(char val) {vaCharacter = val;}public TrieNode() {}public boolean existStr(){return isEnd;}public void setTrue(){isEnd = true;}public TrieNode getChildStr(char val) {if(children.containsKey(val)) {return children.get(val);}return null;}};

参数解释：

1. children：所有子节点组成的val - val的对象的map，查找更方便
2. vaCharacter：该节点的值
3. isEnd：在改节点是否是字符串结尾(是否存在到目前为止前缀形成的字符串，方便区分前缀和字符串)

1. 添加操作

 /** Inserts a word into the trie. */public void insert(String word) {TrieNode exangeNode = root;for(int i = 0; i < word.length(); i++){TrieNode temp = exangeNode.getChildStr(word.charAt(i));if(temp == null){exangeNode.children.put(word.charAt(i),new TrieNode());}else{}exangeNode = exangeNode.getChildStr(word.charAt(i));}exangeNode.setTrue();}

2. 查串操作（查询字符串是否存在于前缀树）

public boolean search(String word) {TrieNode exangeNode = root;for(int i = 0; i < word.length(); i++){TrieNode temp = exangeNode.getChildStr(word.charAt(i));if(temp == null){return false;}else{exangeNode = exangeNode.getChildStr(word.charAt(i));}}return exangeNode.existStr();}

3. 查前缀操作（查询前缀是否存在）

    public boolean startsWith(String prefix) {TrieNode exangeNode = root;for(int i = 0; i < prefix.length(); i++){TrieNode temp = exangeNode.getChildStr(prefix.charAt(i));if(temp == null){return false;}else{exangeNode = exangeNode.getChildStr(prefix.charAt(i));}}return true;}

整体实现代码：

class Trie {TrieNode root;/** Initialize your data structure here. */public Trie() {root = new TrieNode();}/** Inserts a word into the trie. */public void insert(String word) {TrieNode exangeNode = root;for(int i = 0; i < word.length(); i++){TrieNode temp = exangeNode.getChildStr(word.charAt(i));if(temp == null){exangeNode.children.put(word.charAt(i),new TrieNode());}else{}exangeNode = exangeNode.getChildStr(word.charAt(i));}exangeNode.setTrue();}/** Returns if the word is in the trie. */public boolean search(String word) {TrieNode exangeNode = root;for(int i = 0; i < word.length(); i++){TrieNode temp = exangeNode.getChildStr(word.charAt(i));if(temp == null){return false;}else{exangeNode = exangeNode.getChildStr(word.charAt(i));}}return exangeNode.existStr();}/** Returns if there is any word in the trie that starts with the given prefix. */public boolean startsWith(String prefix) {TrieNode exangeNode = root;for(int i = 0; i < prefix.length(); i++){TrieNode temp = exangeNode.getChildStr(prefix.charAt(i));if(temp == null){return false;}else{exangeNode = exangeNode.getChildStr(prefix.charAt(i));}}return true;}
}
class TrieNode {public Character vaCharacter;public Map children = new HashMap<>();private boolean isEnd;public TrieNode(char val) {vaCharacter = val;}public TrieNode() {}public boolean existStr(){return isEnd;}public void setTrue(){isEnd = true;}public TrieNode getChildStr(char val) {if(children.containsKey(val)) {return children.get(val);}return null;}};