leetcode-implement-trie-prefix-tree

发表于   |   分类于 ，   |  

题目大意

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

　　实现字典树

题目分析

　　细节实现题，只要理解好trie树概念，自己定义好数据及结构。我这里trie树的节点保存了26个子节点，节点字符，以及词频freq，之所以没有存“是否为叶子节点”的变量，是因为词频能够保留更多的信息。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
class TrieNode {
    
    public TrieNode[] childNodes;
    public int freq;
    public char nodeChar;
    // Initialize your data structure here.
    public TrieNode() {
        childNodes = new TrieNode[26];
        freq = 0;
    }
}
public class Trie {
    private TrieNode root;
    public Trie() {
        root = new TrieNode();
    }
    // Inserts a word into the trie.
    public void insert(String word) {
        if(word.length() == 0) {
            return;
        }
        TrieNode cur = root;
        for(int i = 0; i < word.length(); i++) {
            int k = word.charAt(i) - 'a';
            if(cur.childNodes[k] == null) {
            	cur.childNodes[k] = new TrieNode();
            	cur.childNodes[k].nodeChar = word.charAt(i);
            }
            cur = cur.childNodes[k];
            if(i == word.length() - 1) {
            	cur.freq ++;
            }
        }
    }
    // Returns if the word is in the trie.
    //root->'a'->'b'->'c'
    public boolean search(String word) {
        if(word.length() == 0) {
        	return false;
        }
        TrieNode cur = root;
        for(int i = 0; i < word.length(); i++) {
            int k = word.charAt(i) - 'a';
            if(cur.childNodes[k] == null) {
                return false;
            }
            cur = cur.childNodes[k];
        }
        if(cur.freq > 0) {
        	return true;
        } else {
        	return false;
        }
    }
    // 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;
        }
        TrieNode cur = root;
        for(int i = 0; i < prefix.length(); i++) {
            int k = prefix.charAt(i) - 'a';
            if(cur.childNodes[k] == null) {
                return false;
            }
            cur = cur.childNodes[k];
        }
        return true;
    }
//    public static void main(String[] args) {
//		Trie trie = new Trie();
//		trie.insert("abc");
//		trie.insert("def");
//		System.out.println(trie.search("a"));
//		System.out.println(trie.search("abc"));
//		System.out.println(trie.search("d"));
//		System.out.println(trie.search("def"));
//		System.out.println("---------------------");
//		System.out.println(trie.startsWith("a"));
//		System.out.println(trie.startsWith("abc"));
//		System.out.println(trie.startsWith("d"));
//		System.out.println(trie.startsWith("def"));
//		System.out.println(trie.startsWith(""));
//
//	}
}