字典树-TrieTree

发表于 | 分类于
字数统计: 322

基本概念

字典树是一种有序的树状结构，每个节点表示字符与字符串。字典树可以合并储存有相同前缀的字符串。常用于解决前缀匹配和字串查找的问题。是一种牺牲空间换取时间的做法。

  • 插入
    字串长度的时间
    插入一个新单词
  • 查找
    单词长度的时间
    查找是否存在某单词
    查找是否存在某前缀

实现

通过HashMap实现子节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class TrieNode {
    String word;
    HashMap<Character, TrieNode> children;
    public TrieNode() {
        children = new HashMap<>();
    }
}

class TrieTree {
    public TrieNode root;
    public TrieTree(TrieNode root) {
        this.root = root;
    }
    public void insert(String word) {
        TrieNode cur = root;
        for (int i = 0; i < word.length(); i++) {
            if (!cur.children.containsKey(word.charAt(i))) {
                cur.children.put(word.charAt(i), new TrieNode());
            }
            cur = cur.children.get(word.charAt(i));
        }
        cur.word = word;
    }   
}

通过数组实现子节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class TrieNode {
    String word;
    TrieNode[] children;
    public TrieNode() {
        children = new TrieNode[26];
    }
}

class TrieTree {
    public TrieNode root;
    public TrieTree(TrieNode root) {
        this.root = root;
    }
    public void insert(String word) {
        TrieNode cur = root;
        for (int i = 0; i < word.length(); i++) {
            if (cur.children[word.charAt(i) - 'a'] == null) {
                cur.children[word.charAt(i) - 'a'] = new TrieNode();
            }
            cur = cur.children[word.charAt(i) - 'a'];
        }
        cur.word = word;
    }   
}

Lintcode相关练习

Word Search II
Palindrome Pairs
K-Edit Distance
Boggle Game