算法：字典树 (转自九章算法)

2023-09-17 03:22 由功夫熊猫发表于 #其他

https://www.jiuzhang.com/solution/implement-trie/

算法：字典树

思路：

题目要求实现一个Trie，包含插入、查找和查找前缀三个方法。
Trie树也称字典树，因为其效率很高，所以在在字符串查找、前缀匹配等中应用很广泛，其高效率是以空间为代价的。
原理：利用串构建一个字典树，这个字典树保存了串的公共前缀信息，因此可以降低查询操作的复杂度。
定义结点Node里包含一个isWord(表示这个结点是否是一个单词的结尾)和一个大小为26的next。

1.定义一个根结点root作为整棵树的查找起点。

2.比如插入一个单词apple：

我们从root开始，依次往下查找a,p,p,l,e：如果在结点n的下一个字母里没有找到我们想要的字母ch，我们就增加新结点到结点n的next[]，式子next[ch-'a']=new Node()。

3.查找一个单词app：

我们从root开始，依次往下查找a,p,p：如果在结点n的下一个字母里没有找到我们想要的字母ch，那么说明不存在，返回False;如果有，那么继续往下找，直到查找的单词app找到最后一位，这时候我们判断一下这个位置的isWord是否为True，如果为True说明这是一个完整单词，否则只是部分，返回False。

4.查找一个前缀

查找一个前缀和查找一个单词的区别就是，当我们想要查找的前缀找到最后一位，不需要判断是否是完整的单词，直接返回True即可。如果不能全部找到则返回False。

复杂度

空间复杂度:字典树每个节点都需要用一个大小为26的数组来存储子节点的指针，所以空间复杂度较高。
时间复杂度：假设所有插入字符串长度之和为n，构建字典树的时间复杂度为O(n)；假设要查找的所有字符串长度之和为k，查找的时间复杂度为O(k)。因此时间复杂度为O(n+k)

java

c++

python

public class Trie {
    private class Node{
        // isWord表示这个结点是否为一个单词的结尾
        // next[]表示这个结点的下一个26个字母结点
        public boolean isWord;  
        public Node[] next; 
        
        public Node() {
            this.isWord = false;
            this.next = new Node[26];
        }
    }
    
    private Node root;
    
    public Trie() {
        root = new Node(); 
    }

    /*
     * @param word: a word
     * @return: nothing
     */
    public void insert(String word) {
        Node now = root;
        int n = word.length();
        for (int i = 0; i < n; i++) {
            // 依次寻找每个字符
            // 如果所有下一个结点中没有当前字符，则增加新结点到下一个next[pos]
            int pos = word.charAt(i) - 'a';
            if (now.next[pos] == null) {
                now.next[pos] = new Node();
            }
            now = now.next[pos];
        }
        now.isWord = true;
    }

    /*
     * @param word: A string
     * @return: if the word is in the trie.
     */
    public boolean search(String word) {
        // 查找单词
        int n = word.length();
        Node now = root;
        for (int i = 0; i < n; i++) {
            int ch = word.charAt(i) - 'a';
            // 如果有下一个对应字符的结点，那么继续查找下一个结点
            // 如果没有下一个对应字符的结点，那么说明查找单词失败
            if (now.next[ch] != null) {
                now = now.next[ch];
            }
            else {
                return false;
            }
        }
        // 如果每个字符都有且是完整单词，才说明查找单词成功
        return now.isWord;
    }

    /*
     * @param prefix: A string
     * @return: if there is any word in the trie that starts with the given prefix.
     */
    public boolean startsWith(String prefix) {
        // 查找前缀
        int n = prefix.length();
        Node now = root;
        for (int i = 0; i < n; i++) {
            int ch = prefix.charAt(i) - 'a';
            // 如果有下一个对应字符的结点，那么继续查找下一个结点
            // 如果没有下一个对应字符的结点，那么说明查找前缀失败
            if (now.next[ch] != null) {
                now = now.next[ch];
            }
            else {
                return false;
            }
        }
        return true;
    }
}

赞同

令狐冲精选

更新于 6/9/2021, 6:57:33 PM

Trie(前缀树) 的模板应用.

维基百科: https://zh.wikipedia.org/zh-hans/Trie

class TrieNode {
public:
    // Initialize your data structure here.
    TrieNode() {
        for (int i = 0; i < 26; i++)
            next[i] = NULL;
        isString = false;
    }
    TrieNode *next[26];
    bool isString;
};
 
class Trie {
public:
    Trie() {
        root = new TrieNode();
    }
 
    // Inserts a word into the trie.
    void insert(string word) {
        TrieNode *p = root;
        for (int i = 0; i < word.size(); i++) {
            if (p->next[word[i]-'a'] == NULL) {
                p->next[word[i]-'a'] = new TrieNode();
            }
            p = p->next[word[i]-'a'];
        }
        p->isString = true;
    }
 
    // Returns if the word is in the trie.
    bool search(string word) {
        TrieNode *p = root;
        for (int i = 0; i < word.size(); i++) {
            if (p == NULL) return false;
            p = p->next[word[i]-'a'];
        }
        if (p == NULL || p->isString == false) 
            return false;
        return true;
         
    }
 
    // Returns if there is any word in the trie
    // that starts with the given prefix.
    bool startsWith(string prefix) {
        TrieNode *p = root;
        for (int i = 0; i < prefix.size(); i++) {
            p = p->next[prefix[i]-'a'];
            if (p == NULL) return false;
        }
        return true;
    }
 
private:
    TrieNode* root;
};

赞同

令狐冲精选

更新于 6/9/2020, 4:03:58 AM

Trie(前缀树) 的模板应用.

维基百科: https://zh.wikipedia.org/zh-hans/Trie

// Version 1: Array of TrieNode
class TrieNode {
    private TrieNode[] children;
    public boolean hasWord;
    
    public TrieNode() {
        children = new TrieNode[26];
        hasWord = false;
    }
    
    public void insert(String word, int index) {
        if (index == word.length()) {
            this.hasWord = true;
            return;
        }
        
        int pos = word.charAt(index) - 'a';
        if (children[pos] == null) {
            children[pos] = new TrieNode();
        }
        children[pos].insert(word, index + 1);
    }
    
    public TrieNode find(String word, int index) {
        if (index == word.length()) {
            return this;
        }
        
        int pos = word.charAt(index) - 'a';
        if (children[pos] == null) {
            return null;
        }
        return children[pos].find(word, index + 1);
    }
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    public void insert(String word) {
        root.insert(word, 0);
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        TrieNode node = root.find(word, 0);
        return (node != null && node.hasWord);
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        TrieNode node = root.find(prefix, 0);
        return node != null;
    }
}

// Version 2: HashMap Version, this version will be TLE when you submit on LintCode
class TrieNode {
    // Initialize your data structure here.
    char c;
    HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();
    boolean hasWord;
    
    public TrieNode(){
        
    }
    
    public TrieNode(char c){
        this.c = c;
    }
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    public void insert(String word) {
        TrieNode cur = root;
        HashMap<Character, TrieNode> curChildren = root.children;
        char[] wordArray = word.toCharArray();
        for(int i = 0; i < wordArray.length; i++){
            char wc = wordArray[i];
            if(curChildren.containsKey(wc)){
                cur = curChildren.get(wc);
            } else {
                TrieNode newNode = new TrieNode(wc);
                curChildren.put(wc, newNode);
                cur = newNode;
            }
            curChildren = cur.children;
            if(i == wordArray.length - 1){
                cur.hasWord= true;
            }
        }
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        if(searchWordNodePos(word) == null){
            return false;
        } else if(searchWordNodePos(word).hasWord) 
          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(searchWordNodePos(prefix) == null){
            return false;
        } else return true;
    }
    
    public TrieNode searchWordNodePos(String s){
        HashMap<Character, TrieNode> children = root.children;
        TrieNode cur = null;
        char[] sArray = s.toCharArray();
        for(int i = 0; i < sArray.length; i++){
            char c = sArray[i];
            if(children.containsKey(c)){
                cur = children.get(c);
                children = cur.children;
            } else{
                return null;
            }
        }
        return cur;
    }
}

赞同

令狐冲精选

更新于 6/9/2020, 4:03:58 AM

代码兼容Python 2 & 3 新建一个 TrieNode 的 class 用于表示 Trie 中的节点，包含 children 和 is_word 两个属性

Trie(前缀树) 的模板应用.

维基百科: https://zh.wikipedia.org/zh-hans/Trie

class TrieNode:
    
    def __init__(self):
        self.children = {}
        self.is_word = False
    
    
class Trie:
    
    def __init__(self):
        self.root = TrieNode()

    """
    @param: word: a word
    @return: nothing
    """
    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        
        node.is_word = True

    """
    return the node in the trie if exists 
    """
    def find(self, word):
        node = self.root
        for c in word:
            node = node.children.get(c)
            if node is None:
                return None
        return node
        
    """
    @param: word: A string
    @return: if the word is in the trie.
    """
    def search(self, word):
        node = self.find(word)
        return node is not None and node.is_word

    """
    @param: prefix: A string
    @return: if there is any word in the trie that starts with the given prefix.
    """
    def startsWith(self, prefix):
        return self.find(prefix) is not None

赞同