- Difficulty: Medium
Implement a trie with
insert
, search
, and startsWith
methods.
Note:
You may assume that all inputs are consist of lowercase letters
You may assume that all inputs are consist of lowercase letters
a-z
.
分析: Trie is a tree data structure, which is used for retrieval of a key in a dataset of strings.应用在 Autocomplete,spell-check等
Efficient in: * Finding all keys with a common prefix. *lexicographical order(字典顺序 aab < ab < b.)
思路: Each Tire node can have maximum R(26 for alphabet) links.
-- Insert string by char into tree, if null, create new TrieNode .Once reach end char mark the isEnd true
-- Search the last char must have the isEnd for true
Complexity: O(M=key_length) for insertion & search, M is the length of key
Space: O(alphabet(26)*M*N) N is number of keys in trie
关键字:Trie
相关题: Trie with back-tracking F家
http://rainykat.blogspot.com/2017/01/leetcodef-211-add-and-search-word-data.html
http://rainykat.blogspot.com/2017/01/leetcodef-211-add-and-search-word-data.html
public class Trie { class TrieNode { // Initialize your data structure here. //R links to node children private TrieNode[] links = new TrieNode[26];//simplified to save code private boolean isEnd; } private TrieNode root = new TrieNode(); // Inserts a word into the trie. public void insert(String word) { TrieNode node = root; for(int i=0;i<word.length();i++){ char cur = word.charAt(i); if(node.links[cur-'a']==null) //char to index node.links[cur-'a']= new TrieNode();//default constructor make copy of instance vars node = node.links[cur-'a']; } node.isEnd = true; } // Returns if the word is in the trie. public boolean search(String word) { TrieNode node = root; for(int i=0;i<word.length();i++){ char cur = word.charAt(i); if(node.links[cur-'a']==null)return false; node = node.links[cur-'a']; } return node.isEnd; } // Returns if there is any word in the trie // that starts with the given prefix. public boolean startsWith(String prefix) { TrieNode node = root; for(int i=0;i<prefix.length();i++){ char cur = prefix.charAt(i); if(node.links[cur-'a']==null)return false; node = node.links[cur-'a']; } return true; } } // Your Trie object will be instantiated and called as such: // Trie trie = new Trie(); // trie.insert("somestring"); // trie.search("key");
No comments:
Post a Comment