leetcode-208-Implement-Trie-(Prefix-Tree)

描述

---

Implement a trie with insert, search, and startsWith methods.

Note:
You may assume that all inputs are consist of lowercase letters a-z.

分析

---

前缀树在搜索引擎中应用广泛，可以用作全文检索，搜索提示等等。举个例子，要在一组字符串中搜索一个匹配的字符串（将搜索倒排索引的问题抽象为最简单的形式），如果我们不使用前缀树这样的数据结构的话，复杂度就是 $O(n*m)$，其中，n是搜索的字符串的长度，m是字符串列表的大小。而使用前缀树的话，搜索一个字符串，复杂度是 $O(n)$。前缀树具体的思路是，用根节点到叶子节点的路径表示字符串。

前缀树有很多变型，如后缀树，基数树（Patricia Tree)，crit-bit tree 等等，这里只要求实现前缀树。

解决方案1(Java)

---

class TrieNode{
    public boolean isWord;
    public TrieNode[] next;
    private final int charCount = 26;
    
    public TrieNode() {
        next = new TrieNode[charCount];
    }
}


public class Trie {
    
    private TrieNode root;

    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        if(word == null || word.length() == 0)
            return;
        TrieNode node = root;
        int d = 0;                  // depth/distance
        
        while(d < word.length()) {
            char c = word.charAt(d);
            if(node.next[c - 'a'] == null)
                node.next[c - 'a'] = new TrieNode();
            node = node.next[c - 'a'];
            d++;
        }
        
        node.isWord = true;
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        if(word == null || word.length() == 0)
            return false;
        TrieNode node = root;
        int d = 0;
        
        while(d < word.length()) {
            char c = word.charAt(d);
            if(node.next[c - 'a'] == null)      // did not find char within word
                return false;
            node = node.next[c - 'a'];
            d++;
        }
        
        return node.isWord;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        if(prefix == null || prefix.length() == 0)
            return false;
        TrieNode node = root;
        int d = 0;
        
        while(d < prefix.length()) {
            char c = prefix.charAt(d);
            if(node.next[c - 'a'] == null)      // did not find char within prefix
                return false;
            node = node.next[c - 'a'];
            d++;
        }
        
        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);
 */

解决方案2(Golang)

---

type Trie struct {
    childMap map[byte]*Trie
    isWord bool
}


/** Initialize your data structure here. */
func Constructor() Trie {
    return Trie{
        childMap: make(map[byte]*Trie),
        isWord: false,
    }
}


/** Inserts a word into the trie. */
func (this *Trie) Insert(word string)  {
    if len(word) == 0 {
        return
    }
    currentNode := this
    for i := 0; i < len(word); i++ {
        nextNode, exist := currentNode.childMap[word[i]]
        if exist {
            currentNode = nextNode
        } else {
            newNode := Constructor()
            currentNode.childMap[word[i]] = &newNode
            currentNode = &newNode
        }
    }
    currentNode.isWord = true
}


/** Returns if the word is in the trie. */
func (this *Trie) Search(word string) bool {
    if len(word) == 0 {
        return false
    }
    var current, next *Trie = this, nil
    ok := false
    for i := 0; i < len(word); i++ {
        if next, ok = current.childMap[word[i]]; !ok {
            return false
        }
        current = next
    }
    return next.isWord
}


/** Returns if there is any word in the trie that starts with the given prefix. */
func (this *Trie) StartsWith(prefix string) bool {
    if len(prefix) == 0 {
        return false
    }
    var current, next *Trie = this, nil
    ok := false
    for i := 0; i < len(prefix); i++ {
        if next, ok = current.childMap[prefix[i]]; !ok {
            return false
        }
        current = next
    }
    return true
}


/**
 * Your Trie object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Insert(word);
 * param_2 := obj.Search(word);
 * param_3 := obj.StartsWith(prefix);
 */

可以阅读一下 redisearch 的 trie tree 的代码，感受一下前缀树在搜索引擎中的实际应用，C 语言的代码，非常简洁优雅。

相关问题

---

(M) Add and Search Word - Data structure design

题目来源

Reference

• redisearch
• Trie wiki