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

[Martina001]

class Trie {
    Trie[] children;
    int val;
    public Trie() {
        children = new Trie[26];
        val = -1;
    }

    public void insert(String word) {
        Trie cur = this;
        for(char c:word.toCharArray()){
            if(cur.children[c-'a'] == null){
                cur.children[c-'a'] = new Trie();
            }
            cur = cur.children[c-'a'];
        }
        // 只有结尾处有val值
        cur.val = 1;
    }

    public boolean search(String word) {
        return startWithPrefix(word) != null && startWithPrefix(word).val != -1;
    }

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

    private Trie startWithPrefix(String pre){
        Trie cur = this;
        for(char c:pre.toCharArray()){
            if(cur.children[c-'a'] == null){
                return null;
            }
            cur=cur.children[c-'a'];
        }
        return cur;
    }
}

[hillsonziqiu]

代码

/*
 * @lc app=leetcode.cn id=208 lang=javascript
 *
 * [208] 实现 Trie (前缀树)
 */

// @lc code=start

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

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

/**
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function (prefix) {
  let node = this.children;
  for (const str of prefix) {
    if (!node[str]) {
      return false;
    }
    node = node[str];
  }
  return node;
};

/**
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function (word) {
  const node = this.startsWith(word);
  return node !== null && node.isEnd === 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)
 */
// @lc code=end

复杂度分析

• 时间复杂度：初始化是O(1)，其余 O(n); n是word.length;
• 空间复杂度：O(n); n是word.length;

[xy147]

js代码

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

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

Trie.prototype.search = function(word) {
    const node = this.searchPrefix(word);
    return node !== undefined && node.isEnd !== undefined;
};

Trie.prototype.startsWith = function(prefix) {
    return this.searchPrefix(prefix);
};

[CathyShang]

前缀树，一种树的结构

• 构建树 节点 1. 字符的字典 2. 完整word计数 3. 前缀pre计数
• 插入 从根节点出发，逐个字符插入，没有就创建树
• 搜索 从根节点开始找，逐个字符寻找

• 搜索pre 从根节点逐个字符寻找

  
  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 tmp in word:
          if tmp not in node.children:
              node.children[tmp] = TrieNode()
          node = node.children[tmp]
          node.preCount += 1
      node.count += 1
  
  def search(self, word: str) -> bool:
      node = self.root
      for tmp in word:
          if tmp not in node.children:
              return False
          node = node.children[tmp]
      return node.count > 0
  
  def startsWith(self, prefix: str) -> bool:
      node = self.root
      for tmp in prefix:
          if tmp not in node.children:
              return False
          node = node.children[tmp]
      return node.preCount > 0

时间复杂度: $O(n)$ 待插入(查找) word or pre

空间复杂度: $O(m*n)$ m操作中字符个数，n字符平均长度

[zhiyuanpeng]

class TrieNode:
    def __init__(self):
        # pre to store the # of str prefixed by the nodes from root to current node
        self.pre = 0
        # count to store the # of str formed by the nodes from root to current node
        self.count = 0
        self.children = collections.defaultdict(TrieNode)
class Trie:

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

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            node = node.children[ch]
            node.pre += 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.pre > 0

[Lizhao-Liu]

class TrieNode {
    var children: [Character: TrieNode] = [:]
    var isEndOfWord: Bool = false
}

class Trie {
    private let root: TrieNode
    init() {
        root = TrieNode()
    }

    func insert(_ word: String) {
        var currentNode = root
        for char in word {
            if currentNode.children[char] == nil {
                currentNode.children[char] = TrieNode()
            }
            currentNode = currentNode.children[char]!
        }
        currentNode.isEndOfWord = true
    }

    func search(_ word: String) -> Bool {
        var currentNode = root
        for char in word {
            if currentNode.children[char] == nil {
                return false
            }
            currentNode = currentNode.children[char]!
        }
        return currentNode.isEndOfWord
    }

    func startsWith(_ prefix: String) -> Bool {
        var currentNode = root
        for char in prefix {
            if currentNode.children[char] == nil {
                return false
            }
            currentNode = currentNode.children[char]!
        }
        return true
    }
}

[Dtjk]

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

};