题目
Trie或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。
请你实现 Trie 类：
Trie()初始化前缀树对象。void insert(String word)向前缀树中插入字符串word。boolean search(String word)如果字符串word在前缀树中，返回true（即，在检索之前已经插入）；否则，返回false。boolean startsWith(String prefix)如果之前已经插入的字符串word的前缀之一为prefix，返回true；否则，返回false。
解题思路
方法一：
- 每个节点的存储一个字符，一个链表表示一个字符串；
- 遍历目标字符串看是否每个字符都存在；
方法二：
1.用List存储字符串；
2.查询前缀时遍历每个字符串看是否包含该前缀。
代码展示
class Trie { class TrieNode { boolean end; TrieNode[] tns = new TrieNode[26]; } TrieNode root; public Trie() { root = new TrieNode(); } public void insert(String s) { TrieNode p = root; for(int i = 0; i < s.length(); i++) { int u = s.charAt(i) - 'a'; if (p.tns[u] == null) p.tns[u] = new TrieNode(); p = p.tns[u]; } p.end = true; } public boolean search(String s) { TrieNode p = root; for(int i = 0; i < s.length(); i++) { int u = s.charAt(i) - 'a'; if (p.tns[u] == null) return false; p = p.tns[u]; } return p.end; } public boolean startsWith(String s) { TrieNode p = root; for(int i = 0; i < s.length(); i++) { int u = s.charAt(i) - 'a'; if (p.tns[u] == null) return false; p = p.tns[u]; } return true; } }
class Trie { List<String> data; public Trie() { data = new ArrayList<>(); } public void insert(String word) { data.add(word); } public boolean search(String word) { return data.contains(word); } public boolean startsWith(String prefix) { for (String s : data){ if(s.startsWith(prefix)){ return true; } } return false; } }
