leetcode208

保护私人版权，尊重他人版权。转载请注明出处并附带页面链接

https://leetcode.com/problems/implement-trie-prefix-tree/

题目要求：实现前缀树，又称字典树，应用在搜索提示等领域。

实现思路：

（1）使用两个变量，数组child和布尔型变量isWord，通过数组将字符串连接起来，如果是null说明不存在，isWord标志当前是否是一个被输入单词的结尾。题目给定字符范围为a-z，创建26大小的child数组（不一定26位全用上，可以用链表优化，只是查找的时候需要遍历链表，牺牲一丢丢的时间）。

（2）添加单词操作：通过计算当前字符-‘a’的数组中该下标是否为null，是则创建，否则继续遍历数组的下标结点，重复操作直到添加最后一个字符将isWord置为true。

（3）查找单词操作：通过遍历前缀树，如果能查找到给定字符串的最后一个字符且isWord为true，则说明查找成功，其他情况为查找失败。

（4）查找是否有包含给定前缀的单词操作：通过遍历前缀树，如果能查到给定前缀的最后一个字符，则说明查找成功，其他情况为查找失败。

import java.util.Arrays;

class Trie {
    Trie child[]=new Trie[26];
	boolean isWord;

	/** Initialize your data structure here. */
    public Trie() {
    	Arrays.fill(child, null);
		isWord = false;
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
    	Trie node = this;
        for (int i = 0; i < word.length(); i++) {
			int index = word.charAt(i) -'a';
			if(node.child[index] == null){
				node.child[index] = new Trie();
			}
			node = node.child[index];
			if(i == word.length() - 1){
				node.isWord = true;
			}
		}
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
    	if (word.length()==0) {
			return false;
		}
    	Trie node = this;
    	for (int i = 0; i < word.length(); i++) {
    		int index = word.charAt(i)-'a';
			if(node.child[index] == null){
				return false;
			}
			node=node.child[index];
		}
    	if(!node.isWord){
    		return false;
    	}
		return true;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
    	if (prefix.length() == 0) {
			return false;
		}
    	Trie node = this;
    	for (int i = 0; i < prefix.length(); i++) {
    		int index = prefix.charAt(i)-'a';
			if(node.child[index] == null){
				return false;
			}
			node=node.child[index];
		}
		return true;
    }
}


/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

Sub

扫码关注微信公众号，随时随地，掌握最新技术资讯

微信