【Day 73 】2021-11-21 - 实现 Trie (前缀树

[azl397985856]

实现 Trie (前缀树

入选理由

暂无

题目地址

leetcode-cn.com/problems/implement-trie-prefix-tree

前置知识

• 树
• Trie

题目描述

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

示例:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple"); // 返回 true
trie.search("app"); // 返回 false
trie.startsWith("app"); // 返回 true1
trie.insert("app");
trie.search("app"); // 返回 true
说明:

你可以假设所有的输入都是由小写字母 a-z 构成的。
保证所有输入均为非空字符串。

[yanglr]

思路:

首先我们需要自己定义一个struct -> TrieNode。

完整单词，会加一个 flag (isWord)。

由于题目说了，word 和 prefix 仅由小写英文字母组成，于是可以选择用size为26的vector<TreeNode>来实现，当然也可以用哈希表来实现。

代码:

实现语言: C++

class Trie {
public:
    /** Initialize your data structure here. */
    Trie() : _root(new TrieNode()) {}
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        TrieNode* p = _root.get();
        for (auto ch : word)
        {
            if (!p->children[ch-'a'])
                p->children[ch-'a'] = new TrieNode();
            p = p->children[ch - 'a'];
        }
        p->isWord = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        const TrieNode* p = find(word);
        return p && p->isWord; // p != nullptr && p->isWord
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        return find(prefix) != nullptr;
    }

private:
    struct TrieNode
    {        
        bool isWord;
        vector<TrieNode*> children;                
        TrieNode(): isWord(false), children(26, nullptr) {}
        ~TrieNode()
        {
            for (auto child : children)
                if (child) delete child;
        }
    };
    std::unique_ptr<TrieNode> _root;
    
    const TrieNode* find(const string& prefix)
    {
        TrieNode* p = _root.get();
        for (auto ch : prefix)
        {
            p = p->children[ch-'a'];
            if (p == nullptr) break;
        }
        return p;
    }
};

复杂度分析:

• 时间复杂度：O(L)，L 是字符串长度， insert search startsWith 操作都是。
• 空间复杂度：O(M^L)，L 是字符串长度，M 是字符集中字符个数，如本题中 M 就是 26。

[a244629128]

class Trie {
    constructor() {
        this.root = new Node();
    }
    
    insert(word) {
        const node = this.traverse(word, true);
        node.setTerminal();
    }
    
    search(word) {
        const node = this.traverse(word);
        if(!node) return false;
        return node.isTerminal;
    }
    
    startsWith(prefix) {
        const node = this.traverse(prefix);
        return !node ? false : true;
    }
    
    traverse(str, append = false) {
        let node = this.root;
        for(const letter of str) {
            if(!node.hasLetter(letter)) {
                if(!append) return null;
                node.addLetter(letter);
            }
            node = node.getLetter(letter);
        }
        
        return node;
    }
}

class Node {
    constructor(letter = null) {
        this.letter = letter;
        this.children = new Map(); 
        this.terminal = false;
    }
    
    addLetter(letter) {
        const node = new Node(letter);
        this.children.set(letter, node);
    }
    
    getLetter(letter) {
        if(!this.hasLetter(letter)) return null;
        return this.children.get(letter);
    }
    
    hasLetter(letter) {
        return this.children.has(letter);
    }
    
    get isTerminal() {
        return this.terminal;
    }
    
    setTerminal() {
        this.terminal = true;
    }
}

[zhangzz2015]

思路

• 建立一个N 叉树，N 为 26，表示某个字母的位置，另外每个节点记录count，表面有以这个节点结尾的word，同时记录preCount，表示有这个word所有出现的字母的位置都计数，preCount可用来标注是否是prefix，另外root节点是个虚拟的头指针，不记录任何单词。举例说明 abc。会形成root->child[0] root->child[0]->child[1] root->child[0]->child[1]->child[2] 每个节点的preCount = 1，最后叶子节点count = 1;

关键点

代码

• 语言支持：C++

C++ Code:

struct triNode
{
    vector<triNode*> child; 
    int preCount; 
    int count; 
    triNode()
    {
        child.assign(26, NULL);
        preCount=0; 
        count =0; 
    }
};
class Trie {
public:
    triNode* root; 
    Trie() {
        
        root = new triNode;
    }
    
    void insert(string word) {
        
        triNode* current = root; 
        
        for(int i=0; i< word.size(); i++)
        {
            int index = word[i]-'a'; 
            if(current->child[index])
            {
                current->child[index]->preCount++; 
            }
            else
            {
                current->child[index] = new triNode; 
                current->child[index]->preCount++; 
            }
            current = current->child[index]; 
        }
        
        current->count++;
    }
    
    bool search(string word) {
        triNode* current = root; 
        for(int i=0; i< word.size(); i++)
        {
            int index = word[i] - 'a'; 
            if(current->child[index])
            {
                current  = current->child[index]; 
            }
            else 
                return false; 
        }
        return current->count>0; 
        
    }
    
    bool startsWith(string prefix) {
        triNode* current = root; 
        for(int i=0; i< prefix.size(); i++)
        {
            int index = prefix[i] - 'a'; 
            if(current->child[index])
            {
                current = current->child[index]; 
            }
            else
                return false; 
        }
        
        return current->preCount>0; 
        
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

[ZacheryCao]

Idea:

Trie.

Code:

class TrieNode:
    def __init__(self):
        self.count = 0
        self.precount = 0
        self.children = {}

class Trie:

    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
            node.precount += 1
        node.count += 1

    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.count > 0

    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.precount > 0

Complexity:

Build the Trie:
Time: O(m * n). m is the average length of the keys. n is the amount of the keys. In other words, it is also the total length of all keys.
Space: O(m * n)
Insert a key:
Time: O(M). M is the length of the key.
Space: O(M)
Search a key or a prefix:
Time: O(M). M is the length of the key or the prefix
Space: O(1)

[ginnydyy]

Problem

https://leetcode.com/problems/implement-trie-prefix-tree/

Note

• Trie is used for searching words or prefixes of words. When the words have many common prefixes, it's more efficient than hash map. And hash map cannot be used to search prefixes.
• Details:
  • The structure of the trie
  • The content of a trie node
  • The constraints of the words, i.e. 26 lower English characters

Solution

class Trie {
    private TrieNode root;

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

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

    public boolean search(String word) {
        TrieNode node = this.root;
        for(int i = 0; i < word.length(); i++){
            if(node.children[word.charAt(i) - 'a'] == null){
                return false;
            }
            node = node.children[word.charAt(i) - 'a'];
        }
        return node.count > 0;
    }

    public boolean startsWith(String prefix) {
        TrieNode node = this.root;
        for(int i = 0; i < prefix.length(); i++){
            if(node.children[prefix.charAt(i) - 'a'] == null){
                return false;
            }
            node = node.children[prefix.charAt(i) - 'a'];
        }
        return node.preCount > 0;
    }

    class TrieNode {
        int count; // the number of words which end with this TreeNode
        int preCount; // the number of prefixs which contain this TreeNode
        TrieNode[] children;
        public TrieNode(){
            this.count = 0;
            this.preCount = 0;
            this.children = new TrieNode[26];
        }
    }
}

/**
 * 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);
 */

Complexity

• Time:
  • Insert: O(n). n is the length of the word to insert.
  • Search word: O(n). n is the length of the word to search.
  • Search prefix: O(n). n is the length of the prefix to search.
• Space: O(m). m is the number of nodes in the trie, which is the number of the characters of all the words inserted.

[thinkfurther]

代码

class Node:
    def __init__(self):
        self.count = 0
        self.preCount = 0
        self.children = {}

class Trie:
    def __init__(self):
        self.root = Node()
    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = Node()
            node = node.children[ch]
            node.preCount += 1
        node.count += 1  
    def search(self, word: str) -> bool:
        current = self.root
        for ch in word:
            if ch not in current.children:
                return False
            current = current.children[ch]
        return current.count > 0
    def startsWith(self, prefix: str) -> bool:
        current = self.root
        for ch in prefix:
            if ch not in current.children:
                return False
            current = current.children[ch]
        return current.preCount > 0

[zhangzhengNeu]

struct triNode
{
vector<triNode*> child;
int preCount;
int count;
triNode()
{
child.assign(26, NULL);
preCount=0;
count =0;
}
};
class Trie {
public:
triNode* root;
Trie() {

    root = new triNode;
}

void insert(string word) {
    
    triNode* current = root; 
    
    for(int i=0; i< word.size(); i++)
    {
        int index = word[i]-'a'; 
        if(current->child[index])
        {
            current->child[index]->preCount++; 
        }
        else
        {
            current->child[index] = new triNode; 
            current->child[index]->preCount++; 
        }
        current = current->child[index]; 
    }
    
    current->count++;
}

bool search(string word) {
    triNode* current = root; 
    for(int i=0; i< word.size(); i++)
    {
        int index = word[i] - 'a'; 
        if(current->child[index])
        {
            current  = current->child[index]; 
        }
        else 
            return false; 
    }
    return current->count>0; 
    
}

bool startsWith(string prefix) {
    triNode* current = root; 
    for(int i=0; i< prefix.size(); i++)
    {
        int index = prefix[i] - 'a'; 
        if(current->child[index])
        {
            current = current->child[index]; 
        }
        else
            return false; 
    }
    
    return current->preCount>0; 
    
}

};

[JiangyanLiNEU]

JavaScript

var Trie = function() {
    this.child = new Map();
    this.wordEnd = false;
};

Trie.prototype.insert = function(word) {
    let cur = this;
    word.split('').forEach(char =>{
        if (cur.child.has(char) === true){
            cur = cur.child.get(char);
        }else{
            cur.child.set(char, new Trie());
            cur = cur.child.get(char);
        };
    });
    cur.wordEnd = true;
};

Trie.prototype.search = function(word) {
    let cur = this;
    let result = true;
    word.split('').forEach(char=> {
        if (cur.child.has(char)===true){
            cur = cur.child.get(char);
        }else{
            result = false;
        };
    });
    return result === false ? false : cur.wordEnd;
};
Trie.prototype.startsWith = function(prefix) {
    let cur = this;
    let result = true;
    prefix.split('').forEach(i => {
        if (cur.child.has(i)===true){
            cur = cur.child.get(i);
        }else{
            result = false;
        };
    });
    return result;
};

Python

class Trie(object):
    def __init__(self):
        self.child = {}
        self.wordEnd = False;
    def insert(self, word):
        cur = self
        for i in word:
            if i not in cur.child:
                cur.child[i] = Trie()
            cur = cur.child[i]
        cur.wordEnd = True
    def search(self, word):
        cur = self
        for i in word:
            if i not in cur.child:
                return False
            cur = cur.child[i]
        return cur.wordEnd
    def startsWith(self, prefix):
        cur = self
        for p in prefix:
            if p not in cur.child:
                return False
            cur = cur.child[p]
        return True

[q815101630]

补作业啦

Trie 树还是很好用的！把每个character 存进trie 树，searc如果最后发现 end 在 cur 里，说明当前词语存在过！而startwith 怒需要考虑 end 只需要考虑最后能成功遍历完prefix

class Trie:

    def __init__(self):
        self.root = {}

    def insert(self, word: str) -> None:
        cur = self.root
        for char in word:
            if char in cur:
                cur = cur[char]
            else:
                cur[char] = {}
                cur = cur[char]
        cur['end'] = word

    def search(self, word: str) -> bool:
        cur = self.root
        for char in word:
            if char in cur:
                cur = cur[char]
            else:
                return False
        if 'end' in cur:
            return True
        return False

    def startsWith(self, prefix: str) -> bool:
        cur = self.root
        for char in prefix:
            if char in cur:
                cur = cur[char]
            else:
                return False
        return True


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

时间空间 所有操作皆 O(n)

[leungogogo]

• Java

class Trie {
    private class TrieNode {
        private char c;
        private Map<Character, TrieNode> map;
        private boolean isEnd;
        
        TrieNode(char ch) {
            c = ch;
            map = new HashMap<>();
            isEnd = false;
        }
    }
    
    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 (!search(word)) {
            TrieNode cur = root;
            for (int i = 0; i < word.length(); ++i) {
                if (!cur.map.containsKey(word.charAt(i))) {
                    cur.map.put(word.charAt(i), new TrieNode(word.charAt(i)));
                }
                cur = cur.map.get(word.charAt(i));
            }
            cur.isEnd = true;
        }
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode cur = root;
        for (int i = 0; i < word.length(); ++i) {
            if (!cur.map.containsKey(word.charAt(i))) {
                return false;
            }
            cur = cur.map.get(word.charAt(i));
        }
        
        return cur.isEnd;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode cur = root;
        for (int i = 0; i < prefix.length(); ++i) {
            if (!cur.map.containsKey(prefix.charAt(i))) return false;
            cur = cur.map.get(prefix.charAt(i));
        }
        return true;
    }
}

[yachtcoder]

class TrieNode:
    def __init__(self):
        self.children = defaultdict()
        self.eow = False

class Trie:
    def __init__(self):
        self.root = TrieNode()        

    def insert(self, word: str) -> None:
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.eow = True

    def search(self, word: str) -> bool:
        node = self.searchPrefix(word)
        return node.eow if node else False

    def searchPrefix(self, prefix):
        node = self.root
        for c in prefix:
            if c in node.children:
                node = node.children[c]
            else:
                return None
        return node

    def startsWith(self, prefix: str) -> bool:
        return self.searchPrefix(prefix) != None
        

[mixtureve]

class Trie {
    
    class TrieNode {
        TrieNode[] children;
        boolean isWord;
        
        public TrieNode() {
            children = new TrieNode[26];
            isWord = false;
        }
    }
    
    private TrieNode root;
    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
    }
    
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode cur = root;
        
        for (int i = 0; i < word.length(); i++) {
            char c  = word.charAt(i);
            TrieNode next = cur.children[c - 'a'];
            if (next == null) {
                next = new TrieNode();
                cur.children[c - 'a'] = next;
            } 
            cur = next;
        }
        cur.isWord = true;
        
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode cur = root;
        for (int i = 0; i < word.length(); i++) {
            TrieNode next = cur.children[word.charAt(i) - 'a'];
            if (next == null) {
                return false;
            } 
            cur = next;
        }
        return cur.isWord == true;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode cur = root;
        for (int i = 0; i < prefix.length(); i++) {
            TrieNode next = cur.children[prefix.charAt(i) - 'a'];
            if (next == null) {
                return false;
            } 
            cur = next;
        }
        return true;
    }
}

[biancaone]

class TrieNode:
    def __init__(self):
        self.is_word = False
        self.children = collections.defaultdict(TrieNode)
        
        
class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        node = self.root
        for c in word:
            node = node.children[c] 
        node.is_word = True
            
        

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        node = self.find(word)
        return node and node.is_word

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        node = self.find(prefix)
        if node:
            return True
        return False
        
        
    def find(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                return None
            node = node.children[c]
        return node