【Day 73 】2023-01-12 - 实现 Trie (前缀树

[azl397985856]

实现 Trie (前缀树

入选理由

暂无

题目地址

https://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 构成的。 保证所有输入均为非空字符串。

[Ryanbaiyansong]

fhjjtfggfc

[JancerWu]

class Trie {

    class Node {
        Node[] childs;
        boolean end;
        Node() {
            childs = new Node[26];
        }
    }

    Node root;

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

    public void insert(String word) {
        Node cur = root;
        for (char c : word.toCharArray()) {
            Node next = cur.childs[c-'a'];
            if (next == null) {
                cur.childs[c-'a'] = new Node();
            }
            cur = cur.childs[c-'a'];
        }
        cur.end = true;
    }

    public boolean search(String word) {
        Node cur = root;
        for (char c : word.toCharArray()) {
            Node next = cur.childs[c-'a'];
            if (next == null) return false;
            cur = cur.childs[c-'a'];
        }
        return cur.end;
    }

    public boolean startsWith(String prefix) {
        Node cur = root;
        for (char c : prefix.toCharArray()) {
            Node next = cur.childs[c-'a'];
            if (next == null) return false;
            cur = cur.childs[c-'a'];
        }
        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);
 */

[buer1121]

class Trie: def init(self): self.children = [None] * 26 self.isEnd = False

def searchPrefix(self, prefix: str) -> "Trie":
    node = self
    for ch in prefix:
        ch = ord(ch) - ord("a")
        if not node.children[ch]:
            return None
        node = node.children[ch]
    return node

def insert(self, word: str) -> None:
    node = self
    for ch in word:
        ch = ord(ch) - ord("a")
        if not node.children[ch]:
            node.children[ch] = Trie()
        node = node.children[ch]
    node.isEnd = True

def search(self, word: str) -> bool:
    node = self.searchPrefix(word)
    return node is not None and node.isEnd

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

[bookyue]

code

class Trie {
    private final Trie[] children;
    private boolean isEnd;

    public Trie() {
        children = new Trie[26];
        isEnd = false;
    }

    public void insert(String word) {
        Trie node = this;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null)
                node.children[idx] = new Trie();

            node = node.children[idx];
        }

        node.isEnd = true;
    }

    public boolean search(String word) {
        Trie node = searchPrefix(word);
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    private Trie searchPrefix(String prefix) {
        Trie node = this;
        for (char c : prefix.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null)
                return null;

            node = node.children[idx];
        }

        return node;
    }
}

[chenming-cao]

解题思路

前缀树。做法参考讲义，先建立TrieNode类，再建立Trie类，各种方法的实现类似DFS，insert是按照word的字母顺序从Trie的根节点出发建节点，每个在word中出现的字母是其前一个字母的children，建节点的时候更新precount用来记录prefix个数的变量，最后节点全部构建完成更新表示word结尾的节点的count值。search和startsWith需要把Trie的节点和word或者prefix的对应位置的字母相比较，需要满足所有节点都存在，同时对应的precount和count值都大于0。

代码

class Trie {

    class TrieNode {
        int count; // count number of words ending at current TrieNode
        int precount; // count number of words that has a prefix ending at current TrieNode
        TrieNode[] children;

        public TrieNode() {
            children = new TrieNode[26]; // word and prefix contains only of lowercase English letters
            count = 0;
            precount = 0;
        }
    }

    TrieNode root; // starting from root

    public Trie() {
        root = new TrieNode(); // initiate a root
    }

    public void insert(String word) {
        TrieNode node = root; // use node to track the current TrieNode
        // check each letter in word
        for (int i = 0; i < word.length(); i++) {
            char letter = word.charAt(i);
            // check whether a node for current letter exists in the Trie, if not create a TrieNode
            if (node.children[letter - 'a'] == null) {
                node.children[letter - 'a'] = new TrieNode();
            }
            node = node.children[letter - 'a']; // move to the TrieNode representing current letter
            node.precount++; // increment precount of the TrieNode
        }
        node.count++; // after word is inserted in the Trie, increment the count
    }

    public boolean search(String word) {
        TrieNode node = root;
        // check each letter in word
        for (int i = 0; i < word.length(); i++) {
            char letter = word.charAt(i);
            // if letter does not show up in the corresponding position
            if (node.children[letter - 'a'] == null) {
                return false;
            }
            node = node.children[letter - 'a']; // move to next TrieNode
        }
        // check whether there is word ending at the node respresenting the last letter of the word
        return node.count > 0;
    }

    public boolean startsWith(String prefix) {
        TrieNode node = root;
        // check each letter in prefix
        for (int i = 0; i < prefix.length(); i++) {
            char letter = prefix.charAt(i);
            // if letter does not show up in the corresponding position
            if (node.children[letter - 'a'] == null) {
                return false;
            }
            node = node.children[letter - 'a']; // move to next TrieNode
        }
        // check whether there is word starting with the prefix
        return node.precount > 0;
    }
}

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

复杂度分析

• 时间复杂度：insert和search为O(len(word))，startsWith为O(len(prefix))
• 空间复杂度：O(T)，T为Trie的总节点数

[Elsa-zhang]

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):
        node = self.root
        for w in word:
            if w not in node.children:
               node.children[w] = TrieNode()
            node = node.children[w]
            node.preCount += 1
        node.count += 1

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

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

# 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)

[Abby-xu]

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

class Trie:

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

def insert(self, word: str) -> None:
    current = self.root
    for letter in word:
        current = current.children[letter]
    current.is_word = True

def search(self, word: str) -> bool:
    current = self.root
    for letter in word:
        current = current.children.get(letter)
        if current is None:
            return False
    return current.is_word

def startsWith(self, prefix: str) -> bool:
    current = self.root
    for letter in prefix:
        current = current.children.get(letter)
        if current is None:
            return False
    return True

[A-pricity]

function Node(val, isEnd){
    this.val = val
    this.child = {}
    this.isEnd = isEnd|| false
}

var Trie = function() {
    this.root = new Node()
};

Trie.prototype.insert = function(word) {
    let cur = this.root
    for (let c of word){
        if (cur.child[c] == null) cur.child[c] = new Node(c)
        cur = cur.child[c]
    }
    cur.isEnd = true;
};

Trie.prototype.search = function(word) {
    let cur = this.root
    for (let c of word){
        if (cur.child[c] == null) return false
        cur = cur.child[c]
    }
    return cur.isEnd
};

Trie.prototype.startsWith = function(prefix) {
    let cur = this.root
    for (let c of prefix){
        if (cur.child[c] == null) return false
        cur = cur.child[c]
    }
    return true
};

[klspta]

class Trie {

    class Node{
        Node[] nexts;
        boolean end;

        public Node(){
            nexts = new Node[26];
            end = false;
        }
    }

    Node root;

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

    public void insert(String word) {
        Node cur = root;
        for(int i = 0; i < word.length(); i++){
            int ne = word.charAt(i) - 'a';
            if(cur.nexts[ne] == null){
                cur.nexts[ne] = new Node();
            }
            cur = cur.nexts[ne];
        }
        cur.end = true;
    }

    public boolean search(String word) {
        Node cur = getNode(word);
        return cur != null && cur.end;
    }

    public boolean startsWith(String prefix) {
        return getNode(prefix) != null;
    }

    private Node getNode(String s){
        Node cur = root;
        for(int i = 0; i < s.length(); i++){
            int n = s.charAt(i) - 'a';
            if(cur.nexts[n] == null){
                return null;
            }
            cur = cur.nexts[n];
        }
        return cur;
    }
}

[paopaohua]

class Trie {
    private Trie[] children;
    private boolean isEnd;

    public Trie() {
        children = new Trie[26];
        isEnd = false;
    }

    public void insert(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        Trie node = searchPrefix(word);
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    private Trie searchPrefix(String prefix) {
        Trie node = this;
        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                return null;
            }
            node = node.children[index];
        }
        return node;
    }
}

[RestlessBreeze]

code

class Trie {
private:
    vector<Trie*> children;
    bool isEnd;

    Trie* searchPrefix(string prefix) {
        Trie* node = this;
        for (char ch : prefix) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {
                return nullptr;
            }
            node = node->children[ch];
        }
        return node;
    }

public:
    Trie() : children(26), isEnd(false) {}

    void insert(string word) {
        Trie* node = this;
        for (char ch : word) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {
                node->children[ch] = new Trie();
            }
            node = node->children[ch];
        }
        node->isEnd = true;
    }

    bool search(string word) {
        Trie* node = this->searchPrefix(word);
        return node != nullptr && node->isEnd;
    }

    bool startsWith(string prefix) {
        return this->searchPrefix(prefix) != nullptr;
    }
};

[mayloveless]

思路

实现一个字典树

代码

var TrieNode = function(data) {
    this.data = data
    this.isEnding = false
    this.children = new Array(26)
}

var Trie = function() {
    this.root = new TrieNode('/')
};

/** 
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function(word) {
    let p = this.root
    for (let c of word) {
        let index = asciiDiff(c, 'a')
        if (p.children[index] == null) {
            p.children[index] = new TrieNode(c)
        }
        p = p.children[index]
    }
    p.isEnding = true
};

/** 
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
    let p = this.root
    for (let c of word) {
        let index = asciiDiff(c, 'a')
        if (p.children[index] == null) {
            return false
        }
        p = p.children[index]
    }
    return p.isEnding
};

/** 
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function(prefix) {
let p = this.root
    for (let c of prefix) {
        let index = asciiDiff(c, 'a')
        if (p.children[index] == null) {
            return false
        }
        p = p.children[index]
    }
    return true
};

var asciiDiff = (a,b) => {
    return a.charCodeAt(0) - b.charCodeAt(0);
}

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

复杂度

时间：O(1) 空间：O（word.length⋅26）

[FlipN9]

/**
    TC: Initialization: O(1)
        others: O(∣S∣)   ∣S∣ 是每次插入或查询的字符串的长度。
    SC： O(∣T∣⋅Σ)        ∣T∣ 为所有插入字符串的长度之和，Σ 为字符集的大小，本题 Σ=26。
*/
class Trie {
    private Trie[] children;
    private boolean isEnd;

    public Trie() {
        children = new Trie[26];
        isEnd = false;          // 区分是否是一个单词的结尾
    }

    public void insert(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
            int c = word.charAt(i) - 'a';
            if (node.children[c] == null) {
                node.children[c] = new Trie();
            }
            node = node.children[c];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        Trie node = searchPrefix(word);
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    private Trie searchPrefix(String prefix) {
        Trie node = this;
        for (int i = 0; i < prefix.length(); i++) {
            int c = prefix.charAt(i) - 'a';
            if (node.children[c] == null) {
                return null;
            }
            node = node.children[c];
        }
        return node;
    }
}

[Jetery]

代码 (cpp)

#define TRIE_MAX_CHAR_NUM 26

struct TrieNode {
    TrieNode *child[TRIE_MAX_CHAR_NUM];
    bool is_end;
    TrieNode() :is_end(false) {
        for (int i = 0; i < TRIE_MAX_CHAR_NUM; i++) {
            child[i] = 0;
        }
    }
};

class Trie {
public:
    /** Initialize your data structure here. */
    Trie() { }

    ~Trie() {
        for (int i = 0; i < _node_vec.size(); i++) {
            delete _node_vec[i];
        }
    }
    /** Inserts a word into the trie. */
    void insert(string word) {
        TrieNode *ptr = &_root;
        int index=0;
        while (word[index]) {
            int pos = word[index] - 'a';
            if (!ptr->child[pos]) {
                ptr->child[pos] = new_node();
            }
            ptr = ptr->child[pos];
            index++;
        }
        ptr->is_end = true;
    }

    /** Returns if the word is in the trie. */
    bool search(string word) {
        TrieNode *ptr = &_root;
        int index=0;
        while (word[index]) {
            int pos = word[index] - 'a';
            if (!ptr->child[pos]) {
                return false;
            }
            ptr = ptr->child[pos];
            index++;
        }
        return ptr->is_end;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        TrieNode *ptr = &_root;
        int index=0;
        while (prefix[index]) {
            int pos = prefix[index] - 'a';
            if (!ptr->child[pos]) {
                return false;
            }
            ptr = ptr->child[pos];
            index++;
        }
        return true;
    }

private:
    TrieNode *new_node() {
        TrieNode *node = new TrieNode();
        _node_vec.push_back(node);
        return node;
    }
    vector<TrieNode*>_node_vec;
    TrieNode _root;
};

[whoam-challenge]

class Trie: def init(self): self.children = [None] * 26 self.isEnd = False

def searchPrefix(self, prefix: str) -> "Trie":
    node = self
    for ch in prefix:
        ch = ord(ch) - ord("a")
        if not node.children[ch]:
            return None
        node = node.children[ch]
    return node

def insert(self, word: str) -> None:
    node = self
    for ch in word:
        ch = ord(ch) - ord("a")
        if not node.children[ch]:
            node.children[ch] = Trie()
        node = node.children[ch]
    node.isEnd = True

def search(self, word: str) -> bool:
    node = self.searchPrefix(word)
    return node is not None and node.isEnd

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

[tiandao043]

class Trie {
private:
    bool isEnd;
    Trie* next[26];
public:
    /** Initialize your data structure here. */
    Trie() {
        isEnd = false;
        memset(next, 0, sizeof(next));
    }

    /** Inserts a word into the trie. */
    void insert(string word) {
        Trie* node = this;
        for(char ch : word){
            if(node->next[ch-'a'] == NULL){
                node->next[ch-'a'] = new Trie();
            }
            node = node->next[ch-'a'];
        }
        node->isEnd = true;

    }

    /** Returns if the word is in the trie. */
    bool search(string word) {
        Trie* node = this;
         for(char ch : word){           
            node = node->next[ch-'a'];
            if(node==NULL){
                return false;
            }
        }
        return node->isEnd;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        Trie* node = this;
        for(char ch : prefix){
            node = node->next[ch-'a'];
            if(node == NULL){
                return false;
            }
        }
        return true;
    }
};

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

[snmyj]

class Trie {
public:
    vector<string> trie;   
    Trie() {

    }

    void insert(string word) {
     trie.push_back(word); 

    }

    bool search(string word) {
      for(int i=0;i<trie.size();i++){
          if(trie[i]==word) return true;
      }  
      return false;
    }

    bool startsWith(string prefix) {
         if(trie.size()==0) return false;
         for(int i=0;i<trie.size();i++){
                 int cnt=0;
             for(int k=0;k<prefix.length();k++){
                 if(prefix[k]==trie[i][k]) {
                     cnt++;
                     continue;
                }
                 else break;
             }
             if(cnt==prefix.length()) return true;
         }   
         return false;
    }
};

[Ryanbaiyansong]

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

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

    def insert(self, word: str) -> None:
        cur = self.root
        for c in word:
            cur = cur.children[c]
        cur.is_word = True
    def search(self, word: str) -> bool:
        cur = self.root
        for c in word:
            if cur is None or c not in cur.children:
                return False 
            cur = cur.children[c]
        return cur.is_word

    def startsWith(self, prefix: str) -> bool:
        cur = self.root 
        for c in prefix:
            if cur is None or c not in cur.children:
                return False
            cur = cur.children[c]
        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)