Trie Tree

Introduction

又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

结点

private class TrieNode{
		boolean isLeaf;	//确定当前节点是否可以成为单词的结尾。
		TrieNode[] childs;
		public TrieNode(){
			childs = new TrieNode[26];	//对应26个字母。
		}
	}

API

1. 插入

    public void insert(String word){
        int len = word.length();
        TrieNode temp = root;
        for(int i = 0; i < len; i++){
            int c = word.charAt(i) - 'a';
            if(temp.childs[c] == null)
                temp.childs[c] = new TrieNode();
            temp = temp.childs[c];
    		}
        temp.isLeaf = true;
    }
   

2. 查找

    public boolean contains(String word){
        int len = word.length();
        TrieNode temp = root;
        for(int i = 0; i < len; i++){
            int c = word.charAt(i) - 'a';
            if(temp.childs[c] == null) return false;
            temp = temp.childs[c];
        }
        return temp.isLeaf;
    }
   

3. 含有前缀

    public boolean hasPrefix(String word){
        int len = word.length();
        TrieNode temp = root;
        for(int i = 0; i < len; i++){
            int c = word.charAt(i) - 'a';
            if(temp.childs[c] == null) return false;
            temp = temp.childs[c];
        }
        return true;
    }
   

Leetcode Questions:

• 208. Implement Trie (Prefix Tree)
• 648. Replace Words
• 676. Implement Magic Dictionary
• 677. Map Sum Pairs
• 720. Longest Word in Dictionary
• 745. Prefix and Suffix Search

Conclusion

1. The Time complexity of trie tree is O(l), where l is the number of characters.
2. Space complexity: O(prefixes) = O(N * L), where N is the number of word and L is the length of each word.
3. Questions are always related to String.
4. Trie tree is still a kind of tree(graph), so we can apply dfs and bfs to it.
5. We need to design our Node class according to the requirements from the questions.

Reference

1. 花花酱 LeetCode 208. Implement Trie (Prefix Tree)