首页 > 代码库 > 208. Implement Trie (Prefix Tree)
208. Implement Trie (Prefix Tree)
Implement a trie with insert
, search
, and startsWith
methods.
Note:
You may assume that all inputs are consist of lowercase letters a-z
.
Show Company Tags
Show Tags
Show Similar Problems
class TrieNode { // Initialize your data structure here. HashMap<Character, TrieNode> map; boolean isWord; public TrieNode() { map = new HashMap<Character, TrieNode>(); isWord = false; } } public class Trie { private TrieNode root; public Trie() { root = new TrieNode(); } // Inserts a word into the trie. public void insert(String word) { TrieNode it = root; for(char c : word.toCharArray()){ if(!it.map.containsKey(c)){ it.map.put(c , new TrieNode() ); } it = it.map.get(c); } it.isWord = true; } // Returns if the word is in the trie. public boolean search(String word) { TrieNode it = root; for(char c : word.toCharArray()){ if(!it.map.containsKey(c)){ return false; } it = it.map.get(c); } return it.isWord; } // Returns if there is any word in the trie // that starts with the given prefix. public boolean startsWith(String prefix) { TrieNode it = root; for(char c : prefix.toCharArray()){ if(!it.map.containsKey(c)){ return false; } it = it.map.get(c); } return true; } } // Your Trie object will be instantiated and called as such: // Trie trie = new Trie(); // trie.insert("somestring"); // trie.search("key");
208. Implement Trie (Prefix Tree)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。