lintcode 实现一个 Trie

比眉伴天荒 2022-07-15 01:27 73阅读 0赞

实现一个 Trie，包含 `insert`, `search`, 和 `startsWith` 这三个方法。

#####  注意事项 #####

你可以假设所有的输入都是小写字母a-z。

您在真实的面试中是否遇到过这个题？

Yes

样例

insert("lintcode")
    search("code") // return false
    startsWith("lint") // return true
    startsWith("linterror") // return false
    insert("linterror")
    search("lintcode) // return true
    startsWith("linterror") // return true

[标签 ][Link 1]

[字典树][Link 2] [脸谱网][Link 3] [优步][Link 4] [谷歌][Link 5]

package tju.chc;
    
    /**
     * Your Trie object will be instantiated and called as such:</br>
     * Trie trie = new Trie();</br>
     * trie.insert("lintcode");</br>
     * trie.search("lint"); will return false</br>
     * trie.startsWith("lint"); will return true
     */
    public class TrieNode {
        // Initialize your data structure here.
    	boolean exist;
    	char ch;
    	TrieNode[] children;
    	
        public TrieNode() {
            
        }
        
        public TrieNode(char ch){
        	this.ch = ch;
        }
    }

package tju.chc;
    
    public class Trie {
        private TrieNode root;
    
        public Trie() {
            root = new TrieNode();
        }
    
        // Inserts a word into the trie.
        public void insert(String word) {
            if(word == null || word.length() == 0){
            	return ;
            }
            TrieNode pre = root;
            for(int i = 0; i < word.length(); i++){
            	
            	int index = word.charAt(i) - 'a';
            	if(pre.children == null){
            		pre.children = new TrieNode[26];
            	}
            	if(pre.children[index] == null){
            		pre.children[index] = new TrieNode(word.charAt(i));
            	}
            	pre = pre.children[index];
            	if(i == word.length() - 1){
            		pre.exist = true;
            	}
            	
            }
        }
    
        // Returns if the word is in the trie.
        public boolean search(String word) {
        	 if (word == null || word.length() == 0) {
        		 return false;
        		}
            TrieNode pre = root;
            if(pre.exist == true)return true;
        	for(int i = 0 ; i < word.length(); i++){
        		int index = word.charAt(i) - 'a'; 
        		if(pre.children == null||pre.children[index] == null){
        			return false;
        		}
        		if (i == word.length() - 1 && pre.children[index].exist == false) {
        			return false;
        		}
        		pre = pre.children[index];
        	}
        	return true;
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        public boolean startsWith(String prefix) {
        	if (prefix == null || prefix.length() == 0) {
        		 return false;
        	}
            TrieNode pre = root;
        	for(int i = 0 ; i < prefix.length(); i++){
        		int index = prefix.charAt(i) - 'a'; 
        		if(pre.children == null ||pre.children[index] == null){
        			return false;
        		}
    
        		pre = pre.children[index];
        	}
        	return true;
        }
    }

[Link 1]: http://www.lintcode.com/zh-cn/problem/implement-trie/#tags
[Link 2]: http://www.lintcode.com/tag/trie/
[Link 3]: http://www.lintcode.com/tag/facebook/
[Link 4]: http://www.lintcode.com/tag/uber/
[Link 5]: http://www.lintcode.com/tag/google/