字典树- TrieTree

基本概念

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

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

实现

• 通过HashMap实现子节点

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;
    }   
}

• 通过数组实现子节点

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