【Day 73 】2023-04-27 - 实现 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 构成的。 保证所有输入均为非空字符串。

[kofzhang]

思路

用字典实现

复杂度

时间复杂度：O(n) 空间复杂度：O(26^n)

代码

class TrieNode:
    def __init__(self):
        self.nodes = defaultdict(TrieNode)
        self.end = False

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.
        """
        t = self.root
        for i in word:            
            t = t.nodes[i] 
        t.end=True

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        t = self.root
        for i in word:
            if i in t.nodes:
                t = t.nodes[i]
            else:
                return False
        return t.end

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        t = self.root
        for i in prefix:
            if i in t.nodes:
                t = t.nodes[i]
            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)

[Diana21170648]

思路

手敲实现前缀树Trie

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 ch in word:
            if ch not in node.children:
                node.children[ch]=TrieNode()
            node=node.children[ch]
            node.precount+=1
        node.count+=1

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

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

**复杂度分析**
- 时间复杂度：O(1)，创建前缀树。
- 空间复杂度：O(字符集的长度*单词的总字符数)

[chanceyliu]

代码

class Trie {
  private children: any;

  constructor() {
    this.children = {};
  }

  insert(word: string): void {
    let node = this.children;
    for (const ch of word) {
      if (!node[ch]) {
        node[ch] = {};
      }
      node = node[ch];
    }
    node.isEnd = true;
  }

  searchPrefix(prefix: string): any {
    let node = this.children;
    for (const ch of prefix) {
      if (!node[ch]) {
        return false;
      }
      node = node[ch];
    }
    return node;
  }

  search(word: string): boolean {
    const node = this.searchPrefix(word);
    return node !== undefined && node.isEnd !== undefined;
  }

  startsWith(prefix: string): boolean {
    return this.searchPrefix(prefix);
  }
}

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

[61hhh]

思路

通过长度为26的Trie数组保存子节点状态，通过标识isEnd记录子节点是否存在叶子节点的情况

代码

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

    public Trie() {
        children = new Trie[26];// 子节点数组记录后面字符可能的26种取值
        isEnd = false;// 根节点默认false
    }

    public void insert(String word) {
        Trie node = this;

        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            if (node.children[index] == null) {
                node.children[index] = new Trie();
            }
            node = node.children[index];// 节点下移
        }
        node.isEnd = true;// 遍历完后 最后节点设置结束标识为真
    }

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

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

    // 搜索前缀字符串 遍历字符串 如果存在就返回最后一个字符节点 否则返回null
    private Trie searchPrefix(String prefix) {
        Trie node = this;
        for (int i = 0; i < prefix.length(); i++) {
            int index = prefix.charAt(i) - 'a';
            if (node.children[index] == null) {
                return null;
            }
            node = node.children[index];
        }
        return node;
    }
}

复杂度分析

• 时间复杂度：创建O(1)，其他O(length)
• 空间复杂度：O(字符的长度和*26)

[csthaha]

var Trie = function() {
    this.children = {}
};

/** 
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function(word) {
    let curNode = this.children;
    for(let str of word) {
        if(!curNode[str]) {
            curNode[str] = {}
        }
        curNode = curNode[str]
    }
    curNode.end = true;
};

/** 
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
    let node = this.children;
    for(let i = 0; i < word.length; i++) {
        const char = word[i];
        if(!node[char]) {
            return false;
        }
        node = node[char];
    }
    return node !== undefined && node.end !== undefined;
};

/** 
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function(prefix) {
    let node = this.children;
    for(let i = 0; i < prefix.length; i++) {
        const char = prefix[i];
        if(!node[char]) {
            return false;
        }
        node = node[char];
    }
    return node !== undefined;
};

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

[FireHaoSky]

思路：字典树

代码：python

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

复杂度分析：

"""
时间复杂度：O(len(word))
空间复杂度：O(∣T∣⋅Σ)
"""

[snmyj]

class Trie { public: vector 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;
}

};

[harperz24]

class TrieNode:
    def __init__(self, char=""):
        self.char = char
        self.children = {}
        self.is_end = False

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

    def insert(self, word: str) -> None:
        cur = self.root
        for ch in word:
            if ch in cur.children:
                cur = cur.children[ch]
            else:
                new_node = TrieNode(ch)
                cur.children[ch] = new_node
                cur = new_node
        cur.is_end = True     

    def search(self, word: str) -> bool:
        cur = self.root
        for ch in word:
            if ch not in cur.children:
                return False
            cur = cur.children[ch]
        # Reach at the end of word.
        # return True if word is present, i.e is_end = True else False
        return cur.is_end

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

[Size-of]

var Trie = function() {
    this.children = {};
};

/** 
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function(word) {
  let node = this.children;
  for (const ch of word) {
      if (!node[ch]) {
          node[ch] = {};
      }
      node = node[ch];
  }
  node.isEnd = true;
};

Trie.prototype.searchPrefix = function(prefix) {
    let node = this.children;
    for (const ch of prefix) {
        if (!node[ch]) {
            return false;
        }
        node = node[ch];
    }
    return node;
}

/** 
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
    const node = this.searchPrefix(word);
    return node !== undefined && node.isEnd !== undefined;
};

/** 
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function(prefix) {
    return this.searchPrefix(prefix);
};

[NorthSeacoder]

/**
 * Initialize your data structure here.
 */
var Trie = function () {
    this.node = {};
};

/**
 * Inserts a word into the trie. 
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function (word) {
    let node = this.node;
    for (let char of word) {
        if (!node[char]) {
            node[char] = {}
        }
        node = node[char]
    }
    node.isWord = true;
};

/**
 * Returns if the word is in the trie. 
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function (word) {
    let node = this.node;
    for (let char of word) {
        if (!node[char]) return false;
        node = node[char]
    }
    return !!node.isWord
};

/**
 * Returns if there is any word in the trie that starts with the given prefix. 
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function (prefix) {
    let node = this.node;
    for (let char of prefix) {
        if (!node[char]) return false;

        node = node[char]
    }
    return true
};

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

[wangqianqian202301]

class TrieNode:
    def __init__(self):
        self.word=False
        self.children={}

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

    def insert(self, word):
        node=self.root
        for i in word:
            if i not in node.children:
                node.children[i]=TrieNode()
            node=node.children[i]
        node.word=True
    def search(self, word):
        node=self.root
        for i in word:
            if i not in node.children:
                return False
            node=node.children[i]
        return node.word
    def startsWith(self, prefix):
        node=self.root
        for i in prefix:
            if i not in node.children:
                return False
            node=node.children[i]
        return True

[RestlessBreeze]

code

class Trie {
    Trie *child[26];
    bool isWord;
public:
    /** Initialize your data structure here. */
    Trie() {
        isWord = false;
        for(int i=0;i<26;i++){
            child[i] = nullptr;
        }
    }

    /** Inserts a word into the trie. */
    void insert(string word) {
        Trie *t = this;
        for(char c: word){
            if(!t -> child[c-'a']){
                t->child[c-'a'] = new Trie();
            }
            t = t->child[c-'a'];
        }
        t->isWord = true;
    }

    /** Returns if the word is in the trie. */
    bool search(string word) {
        Trie *t = this;
        for(char c:word){
            if(!t -> child[c - 'a']){
                return false;
            }
            t = t->child[c - 'a'];
        }
        return t->isWord;
    }

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

[lp1506947671]

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

  class Trie:

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

      def insert(self, word):
          """
          Inserts a word into the trie.
          :type word: str
          :rtype: void
          """
          node = self.root
          for ch in word:
              if ch not in node.children:
                  node.children[ch] = TrieNode()
              node = node.children[ch]
              node.preCount += 1
          node.count += 1

      def search(self, word):
          """
          Returns if the word is in the trie.
          :type word: str
          :rtype: bool
          """
          node = self.root
          for ch in word:
              if ch not in node.children:
                  return False
              node = node.children[ch]
          return node.count > 0

      def startsWith(self, prefix):
          """
          Returns if there is any word in the trie that starts with the given prefix.
          :type prefix: str
          :rtype: bool
          """
          node = self.root
          for ch in prefix:
              if ch not in node.children:
                  return False
              node = node.children[ch]
          return node.preCount > 0

复杂度分析

令 n 为待操作的字符串的长度。

• 时间复杂度：创建 Trie:O(1), 其余操作为 O(n)。
• 空间复杂度：最坏情况下没有任何前缀，此时空间复杂度为所有操作的单词所占的空间，具体来说就是 O(字符集大小*单词总字符数)O(字符集大小∗单词总字符数)。不过随着前缀相同的单词增多，效率会变好。（也就是说如果字符串中的相同前缀比较多，则性能优化明显）

[JasonQiu]

class Trie:
    def __init__(self):
        self.dict = {}

    def insert(self, word: str) -> None:
        current = self.dict
        for c in word:
            if c not in current:
                current[c] = {}
            current = current[c]
        current["#"] = True

    def search(self, word: str) -> bool:
        current = self.dict
        for c in word:
            if c not in current:
                return False
            current = current[c]
        return "#" in current

    def startsWith(self, prefix: str) -> bool:
        current = self.dict
        for c in prefix:
            if c not in current:
                return False
            current = current[c]
        return True

Time: O(1), O(n) Space: O(n*26)

[kangliqi1]

class TrieNode: def init(self): self.count = 0 self.preCount = 0 self.children = {}

class Trie:

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

def insert(self, word):
    """
    Inserts a word into the trie.
    :type word: str
    :rtype: void
    """
    node = self.root
    for ch in word:
        if ch not in node.children:
            node.children[ch] = TrieNode()
        node = node.children[ch]
        node.preCount += 1
    node.count += 1

def search(self, word):
    """
    Returns if the word is in the trie.
    :type word: str
    :rtype: bool
    """
    node = self.root
    for ch in word:
        if ch not in node.children:
            return False
        node = node.children[ch]
    return node.count > 0

def startsWith(self, prefix):
    """
    Returns if there is any word in the trie that starts with the given prefix.
    :type prefix: str
    :rtype: bool
    """
    node = self.root
    for ch in prefix:
        if ch not in node.children:
            return False
        node = node.children[ch]
    return node.preCount > 0

[X1AOX1A]

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

class Trie:

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

    def insert(self, word):
        """
        Inserts a word into the trie.
        :type word: str
        :rtype: void
        """
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
            node.preCount += 1
        node.count += 1

    def search(self, word):
        """
        Returns if the word is in the trie.
        :type word: str
        :rtype: bool
        """
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.count > 0

    def startsWith(self, prefix):
        """
        Returns if there is any word in the trie that starts with the given prefix.
        :type prefix: str
        :rtype: bool
        """
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.preCount > 0

[joemonkeylee]

代码

  public class Trie
        {
            bool isEnd;
            Trie[] childTries = new Trie[26];

            public void Insert(string word)
            {
                Trie current = this;
                foreach (var c in word)
                {
                    current.childTries[c - 'a'] ??= new Trie();
                    current = current.childTries[c - 'a'];
                }

                current.isEnd = true;
            }

            public bool Search(string word)
            {
                Trie current = this;
                foreach (var c in word)
                {
                    if (current.childTries[c - 'a'] == null) return false;
                    current = current.childTries[c - 'a'];
                }

                return current.isEnd;
            }

            public bool StartsWith(string prefix)
            {
                Trie current = this;
                foreach (var c in prefix)
                {
                    if (current.childTries[c - 'a'] == null) return false;
                    current = current.childTries[c - 'a'];
                }

                return true;
            }
        }

[Lydia61]

实现前缀树

思路

前缀树，套路

代码

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;
    }
};

复杂度分析

• 时间复杂度：O(1)
• 空间复杂度：O(26)

[Jetery]

class Trie {
public:
    /** Initialize your data structure here. */
    struct Node
    {
        bool is_end;
        Node *next[26];
        Node()
        {
            is_end = false;
            for (int i = 0; i < 26; i ++ )
                next[i] = 0;
        }
    };

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

    /** Inserts a word into the trie. */
    void insert(string word) {
        Node *p = root;
        for (char c : word)
        {
            int son = c - 'a';
            if (!p->next[son]) p->next[son] = new Node();
            p = p->next[son];
        }
        p->is_end = true;
    }

    /** Returns if the word is in the trie. */
    bool search(string word) {
        Node *p = root;
        for (char c : word)
        {
            if (p->next[c - 'a']) p = p->next[c - 'a'];
            else
                return false;
        }
        return p->is_end;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        Node *p = root;
        for (char c : prefix)
        {
            if (p->next[c - 'a']) p = p->next[c - 'a'];
            else
                return false;
        }
        return true;
    }
};

[bookyue]

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;
    }
}

[bingzxy]

代码实现

class Trie {

    private Node[] root;
    private Node[] cur;

    public Trie() {
        root = new Node[26];
        cur = root;
    }

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

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

    public boolean startsWith(String prefix) {
        cur = root;
        Node curNode = null;
        for (char c :  prefix.toCharArray()) {
            int index = c - 'a';
            if (cur[index] == null) {
                return false;
            }
            curNode = cur[index];
            cur = cur[index].next;
        }
        return true;
    }

    class Node {
        private boolean end;
        private Node[] next = new Node[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);
 */

[Fuku-L]

代码

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

    public void insert(String word) {
         TrieNode node = 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 = 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 = 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;
    }
     private class TrieNode {

        int count; //表示以该处节点构成的串的个数
        int preCount; //表示以该处节点构成的前缀的字串的个数
        TrieNode[] children;

        TrieNode() {

            children = new TrieNode[26];
            count = 0;
            preCount = 0;
        }
    }
}

复杂度分析

• 时间复杂度：O(N)，其中 N 为数组长度。
• 空间复杂度：O(1)

[aoxiangw]

class TrieNode:
    def __init__(self):
        self.children = {}
        self.end = False

class Trie:

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

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

    def search(self, word: str) -> bool:
        cur = self.root
        for w in word:
            if w not in cur.children:
                return False
            cur = cur.children[w]
        return cur.end

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