前缀树
什么是前缀树？
前缀树的代码表示方式：
1. 数组
class TrieNode {
public static final int N = 127;
public TrieNode[] children = new TrieNode[N];
};
2. HashMap
class TrieNode {
public Map
};
实现一个 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 构成的。
保证所有输入均为非空字符串。
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/trie/x04fw7/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
TrieNode root; /** Initialize your data structure here. */ public Trie() { root = new TrieNode(); } /** Inserts a word into the trie. */ public void insert(String word) { TrieNode cur = root; for(int i = 0; i < word.length(); i++) { char ch = word.charAt(i); if(!cur.childMap.containsKey(ch)) { cur.childMap.put(ch, new TrieNode()); } cur = cur.childMap.get(ch); } cur.isWord = true; } /** Returns if the word is in the trie. */ public boolean search(String word) { TrieNode cur = root; for(int i = 0; i < word.length(); i++) { char ch = word.charAt(i); if(!cur.childMap.containsKey(ch)) { return false; } cur = cur.childMap.get(ch); } return cur.isWord; } /** Returns if there is any word in the trie that starts with the given prefix. */ public boolean startsWith(String prefix) { TrieNode cur = root; for(int i = 0; i < prefix.length(); i++) { char ch = prefix.charAt(i); if(!cur.childMap.containsKey(ch)) { return false; } cur = cur.childMap.get(ch); } return true; } }