【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

[kidexp]

thoughts

Trie的实现

code

class TrieNode:
    def __init__(self) -> None:
        self.children = {}
        self.is_end_of_word = False

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

    def search_prefix(self, word: str) -> TrieNode:
        root = self.root
        for char in word:
            if char not in root.children:
                return None
            root = root.children[char]
        return root

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        root = self.root
        for char in word:
            if char not in root.children:
                root.children[char] = TrieNode()
            root = root.children[char]
        root.is_end_of_word = True

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        node = self.search_prefix(word)
        return False if not node or not node.is_end_of_word else True

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        node = self.search_prefix(prefix)
        return False if not node else True

complexity

Search/Insert/StarsWith Time O(len(word))

Space O(n*len(word))

[pophy]

思路

• 字典树

Java Code

class Trie {   
    TrieNode root;
    public Trie() {
        root = new TrieNode();
    }    
    public void insert(String word) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            if (cur.children[c-'a'] == null) {
                cur.children[c-'a'] = new TrieNode();
            }
            cur = cur.children[c-'a'];
        }
        cur.isWord = true;
    }    
    public boolean search(String word) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            if (cur.children[c-'a'] == null) {
                return false;
            }
            cur = cur.children[c-'a'];
        }
        return cur.isWord;
    }    
    public boolean startsWith(String prefix) {
        TrieNode cur = root;
        for (char c : prefix.toCharArray()) {
            if (cur.children[c-'a'] == null) {
                return false;
            }
            cur = cur.children[c-'a'];
        }
        return true;        
    }        
    private static class TrieNode {        
        boolean isWord;
        TrieNode[] children;
        public TrieNode() {
            children = new TrieNode[26];
        }
    }    
}

时间&空间

• 时间
  • O(k) k = word.length()
• 空间 O(nk) n: 单词数量 k: 单词中字符数

[joeytor]

思路

用一个 [None] * 26 来记录单词, 用 self.isEnd 来标记这个节点是不是单词结尾

insert 时, 如果这个 index 是 None, 添加 一个 Trie Node, 然后 把 node 指向下一个对应的 Trie Node, 这样下一个字符就添加到下一个 Node 中

search 时, 遍历字符, 如果没有这个 Node, 返回 False, 否则如果是searchPrefix, 那么 node 存在就是 True, 如果是 search, 那么如果最后一个字符对应的 isEnd 是 True 就返回 True

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(m×n×3^{l−1})$，其中 m 是二维网格的高度，n 是二维网格的宽度，l 是最长单词的长度。我们仍需要遍历 m×n 个单元格，每个单元格在最坏情况下仍需要遍历 $4 * 3^{l-1}$ 条路径

空间复杂度: O(k x l) 其中 k 是 words 的长度，l 是最长单词的长度。最坏情况下，我们需要 O(k × l) 用于存储前缀树

[st2yang]

class Node:
    def __init__(self):
        self.children = {} # char2node
        self.is_end = False

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

    def insert(self, word: str) -> None:
        curr = self.root
        for ch in word:
            if ch not in curr.children:
                curr.children[ch] = Node()
            curr = curr.children[ch]
        curr.is_end = True

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

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

[yingliucreates]

link:

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

代码 Javascript

const Trie = function() {
    this.root = {};
};

/**
 * Inserts a word into the trie. 
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function(word) {
    let node = this.root;
    word.split('').forEach((char)=>{
        if (!node[char]) node[char] = {};
        node = node[char];
    })
    node.isEnd = true;
};

/**
 * Returns if the word is in the trie. 
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
    let node = this.searchNode(word);
    return node!=null?node.isEnd==true:false;
};

/** javaScript
 * 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.searchNode(prefix);
    return node != null;
};

Trie.prototype.searchNode = function(word) {
    let node = this.root;
    for (let char of word.split('')) {
        if (node[char]) {
            node = node[char]
        } else {
            return null;
        }
    }
    return node;
}

复杂度分析

[wangzehan123]

题目地址(208. 实现 Trie (前缀树))

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

题目描述

Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

 

示例：

输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True

 

提示：

1 <= word.length, prefix.length <= 2000
word 和 prefix 仅由小写英文字母组成
insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次

前置知识

公司

• 暂无

思路

关键点

代码

• 语言支持：Java

Java Code:

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

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

[CoreJa]

思路

看了西法的讲义之后才知道前缀树的结构和模式，没什么好说的，前缀树，每个字符作为一个节点，同时该节点可以存放一些统计数据来更好的完成前缀树的功能，比如startwith和search等

代码

class TrieNode:
    def __init__(self):
        self.count = 0
        self.pre_count = 0
        self.children: Dict[str, TrieNode] = {}

class Trie1:

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

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

    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]
        return cur.count > 0

    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 cur.pre_count > 0

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

    def insert(self, word: str) -> None:
        cur = self.root
        for ch in word:
            if ch not in cur:
                cur[ch] = {}
            cur = cur[ch]
        cur["#"] = "#"

    def search(self, word: str) -> bool:
        cur = self.root
        for ch in word:
            if ch in cur:
                cur = cur[ch]
            else:
                return False
        return "#" in cur

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

[erik7777777]

class Trie {
    TrieNode root;

    class TrieNode {
        Map<Character, TrieNode> children;
        String s;
        public TrieNode() {
            children = new HashMap<>();
            s = "";
        }
    }

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

    public void insert(String word) {
        TrieNode p = root;
        for (char c : word.toCharArray()) {
            if (!p.children.containsKey(c)) {
                p.children.put(c, new TrieNode());
            }
            p = p.children.get(c);
        }
        p.s = word;
    }

    public boolean search(String word) {
        TrieNode p = root;
        for (char c : word.toCharArray()) {
            if (!p.children.containsKey(c)) {
                return false;
            }
            p = p.children.get(c);
        }
        return p.s.equals(word);
    }

    public boolean startsWith(String prefix) {
        TrieNode p = root;
        for (char c : prefix.toCharArray()) {
            if (!p.children.containsKey(c)) {
                return false;
            }
            p = p.children.get(c);
        }
        return true;
    }
}
// also can implement with array as map

[florenzliu]

Explanation

For TrieNode:

• count: the number of words that end with the current TrieNode
• precount: the number of words that have the same prefix till the current TrieNode
• children: depending on the composition of the word, can be a list or a dictionary

For Trie:

• root: the root of a tree

Python

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

class Trie: # like a rooted tree

    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 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:
        """
        Returns if the word is in the trie.
        """
        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:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        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)

Complexity:

• Time Complexity: O(n)
• Space Complexity: O(n * m) where n is the length of the longest word and m is the number of words in the list

[wenlong201807]

代码块

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

时间复杂度和空间复杂度

• 时间复杂度 O(n)
• 空间复杂度 O(1)

[chaggle]

---

title: "Day 73 208. 实现 Trie (前缀树)" date: 2021-11-21T09:35:06+08:00 tags: ["Leetcode", "c++", "Trie"] categories: ["91-day-algorithm"] draft: true

---

208. 实现 Trie (前缀树)

题目

Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
 

示例：

输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True
 

提示：

1 <= word.length, prefix.length <= 2000
word 和 prefix 仅由小写英文字母组成
insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次

题目思路

• 1、Trie树的设计模板题目，建议先了解其概念，然后背模板实现，多做几道Trie树的题目即可。

class Trie {
private:
    bool isEnd;
    vector<Trie*> next;
public:
    Trie() : next(26), isEnd(false) {}

    void insert(string word) {
        Trie* T = this;
        for (char c : word) 
        {
            if (T -> next[c - 'a'] == NULL)
            {
                T -> next[c - 'a'] = new Trie();
            }
            T = T -> next[c - 'a'];
        }
        T -> isEnd = true;
    }

    bool search(string word) {
        Trie* T = this;
        for (char c : word) 
        {
            T = T -> next[c - 'a'];
            if (T == NULL) return false;
        }
        return T -> isEnd;
    }

    bool startsWith(string prefix) {
        Trie* T = this;
        for (char c : prefix) 
        {
            T = T -> next[c-'a'];
            if (T == 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);
 */

复杂度

• 时间复杂度：O(1 + |S|)
• 空间复杂度：O(|T| * sum)

[jocelinLX]

class Trie:

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

def insert(self, word: str) -> None:
    Tree=self.Trie
    for a in word:
        if a not in Tree:
            Tree[a]={}
        Tree=Tree[a]
    Tree["#"] = "#"     #单词结束的标志

def search(self, word: str) -> bool:
    Tree=self.Trie
    for a in word:
        if a not in Tree:
            return False
        return True
        Tree=Tree[a]
    if '#' in Tree:
        return True
    else:
        return False
def startsWith(self, prefix: str) -> bool:
    Tree = self.Trie
    for a in prefix:
        if a not in Tree:
            return False
        Tree = Tree[a]
    return True

[tongxw]

思路

多叉树，路径表示单词，节点表示字符是否存在

代码

class Trie {
    Map<Character, Trie> children;
    boolean isWord;

    public Trie() {
        children = new HashMap<>();
        isWord = false;
    }

    public void insert(String word) {
        Trie node = this;
        for (int i=0; i<word.length(); i++) {
            char c = word.charAt(i);
            Trie next = node.children.getOrDefault(c, null);
            if (next == null) {
                next = new Trie();
                node.children.put(c, next);

            }
            node = next;
        }
        node.isWord = true;
    }

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

    public boolean startsWith(String prefix) {
        Trie node = getLastNode(prefix);
        return node != null;
    }

    private Trie getLastNode(String str) {
        Trie node = this;
        for (int i=0; i<str.length(); i++) {
            char c = str.charAt(i);
            Trie next = node.children.getOrDefault(c, null);
            if (next == null) {
                return null;
            }
            node = next;
        }

        return node;
    }
}

TC: insert O(n), search O(n), startWith O(n), n为单词长度 SC: O(26^n)

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

复杂度分析

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

[kennyxcao]

208. Implement Trie (Prefix Tree)

Intuition

• Trie

Code

class Trie {
  /**
   * Initialize your data structure here.
   */
  constructor() {
    this.root = new TrieNode();
  }

  /**
   * Inserts a word into the trie.
   * @param {string} word
   */
  insert(word) { // Time: O(n), Space: O(m^n), m = number of chars, n = length of longest word
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char);
    }
    node.hasWord = true;
  }

  /**
   * Returns if the word is in the trie.
   * @param {string} word
   * @return {boolean}
   */
  search(word) { // Time: O(n), Space: O(1)
    const node = this._getLeafNode(word);
    return !!node && node.hasWord;
  }

  /**
   * Returns if there is any word in the trie that starts with the given prefix.
   * @param {string} prefix
   * @return {boolean}
   */
  startsWith(prefix) { // Time: O(n), Space: O(1)
    return !!this._getLeafNode(prefix);
  }

  /**
   * Gets last TrieNode down the path of the prefix or return null if it does not exist.
   * @param {string} prefix
   * @return {TrieNode}
   */
  _getLeafNode(prefix) { // Time: O(n), Space: O(1)
    let node = this.root;
    for (const char of prefix) {
      if (!node.children.has(char)) return null;
      node = node.children.get(char);
    }
    return node;
  }
}

/**
 * Trie Node Class
 */
class TrieNode {
  constructor() {
    this.children = new Map();
    this.hasWord = false;
  }
}

Complexity Analysis

• Time: O(n)
• Space: O(n)

[lizzy-123]

思路 前缀树：插入过程就是构建前缀树过程。 代码

class Trie {
    bool b_end;//判断是否时单词结束
    Trie * next[26];
public:
    Trie() {
      b_end = false;
      memset(next,0,sizeof(next));
    }

    void insert(string word) {
       Trie * node = this;
       for(char c:word)
       {
           if(node->next[c-'a']==NULL)
               node->next[c-'a'] = new Trie;
            node = node->next[c-'a'];
       }

       node->b_end = true;
    }

    bool search(string word) {
       Trie * node = this;
       for(char c:word)
       {
           if(node->next[c-'a']==NULL)return false;
           node =  node->next[c-'a'];

       }

       return node->b_end;
    }

    bool startsWith(string prefix) {
     Trie * node = this;
     for(char c:prefix)
     {
         node = node->next[c-'a'];
         if(node==NULL)return false;
     }
     return true;
    }
};

复杂度分析 空间复杂度：O(n):n时字符串长度 时间复杂度：O(n)

[littlemoon-zh]

class Trie:

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

    def insert(self, word: str) -> None:
        t = self.trie
        for ch in word:
            if ch not in t:
                t[ch] = {}
            t = t[ch]
        t['#'] = word

    def search(self, word: str) -> bool:
        t = self.trie

        for ch in word:
            if ch in t:
                t = t[ch]
            else:
                return False
        return '#' in t

    def startsWith(self, prefix: str) -> bool:
        t = self.trie
        for ch in prefix:
            if ch in t:
                t = t[ch]
            else:
                return False
        return True

[Francis-xsc]

思路

Trie的建立

代码

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

    /** Inserts a word into the trie. */
    void insert(string word) {
        treeNode* node=head;
        for(auto c : word){
            if(!node->next[c-'a']){
                node->next[c-'a']=new treeNode();
            }
            node=node->next[c-'a'];
        }
        node->isEnd=true;
    }

    /** Returns if the word is in the trie. */
    bool search(string word) {
        treeNode* node=head;
        for(auto c : word){
            if(!node->next[c-'a'])
                return false;
            node=node->next[c-'a'];
        }
        return node->isEnd;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        treeNode* node=head;
        for(auto c : prefix){
            if(!node->next[c-'a'])
                return false;
            node=node->next[c-'a'];
        }
        return node!=nullptr;
    }
};

复杂度分析

• 时间复杂度：初始化为 O(1)，其余操作为 O(|S|)，其中 |S|是每次插入或查询的字符串的长度。
• 空间复杂度：O（∣T∣⋅Σ)，其中 |T| 为所有插入字符串的长度之和，Σ 为字符集的大小，本题 Σ=26。

[simonsayshi]

class TrieNode{
public:
    bool isWord;
    TrieNode* children[26];

    TrieNode() {
        isWord = false;
        for(int i = 0; i < 26;i++) {
            children[i] = NULL;
        }
    }

};

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

    void insert(string word) {
        TrieNode* cur = root;
        for(int i = 0 ; i < word.size();i++) {
            int k = word[i] - 'a';
            if(cur->children[k] == NULL) {
                cur->children[k] = new TrieNode();
            }
            cur = cur->children[k];
        }
        cur->isWord = true;
    }

    bool search(string word) {
        TrieNode* cur = root;
        for(int i = 0 ; i < word.size();i++ ){
            int k = word[i] - 'a';
            if(cur->children[k] == NULL) {
                return false;
            }
            cur = cur->children[k];
        }
        return cur->isWord;
    }

    bool startsWith(string prefix) {
        TrieNode* cur = root;
        for(int i = 0 ; i < prefix.size();i++ ){
            int k = prefix[i] - 'a';
            if(cur->children[k] == NULL) {
                return false;
            }
            cur = cur->children[k];
        }
        return true;
    }
private:
    TrieNode* root;

};

[watermelonDrip]

class Node(object):
    def __init__(self):
        self.children = collections.defaultdict(Node)
        self.isword = False

class Trie(object):

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

    def insert(self, word):
        current = self.root
        for w in word:
            current = current.children[w]
        current.isword = True

    def search(self, word):
        current = self.root
        for w in word:
            current = current.children.get(w)
            if current == None:
                return False
        return current.isword

    def startsWith(self, prefix):
        current = self.root
        for w in prefix:
            current = current.children.get(w)
            if current == None:
                return False
        return True

[Yufanzh]

Algorithm in python 3

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

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

Complexity Analysis

• Time complexity: O(len(key))
• Space complexity: worst case O(M*N) where m = 26 for this problem where all input are in lower letters.

[ABOUTY]

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

[shixinlovey1314]

Title:208. Implement Trie (Prefix Tree)

Question Reference LeetCode

Solution

Code

class Trie {
public:
    Trie() {
        count = 0;
        preCount = 0;
        children = vector<Trie*>(26, NULL);
    }

    void insert(string word) {
        Trie* node = this;
        for(char ch : word) {
            if (node->children[ch - 'a'] == NULL) {
                node->children[ch - 'a'] = new Trie();
            }
            node = node->children[ch - 'a'];
            node->preCount++;
        }
        node->count++;
    }

    bool search(string word) {
        Trie* node = this;
        for(char ch : word) {
            if (node->children[ch - 'a'] == NULL) {
                return false;
            }
            node = node->children[ch - 'a'];
        }
        return node->count > 0;
    }

    bool startsWith(string prefix) {
        Trie* node = this;
        for(char ch : prefix) {
            if (node->children[ch - 'a'] == NULL) {
                return false;
            }
            node = node->children[ch - 'a'];
        }
        return node->preCount > 0;
    }

private:
    int count;
    int preCount;
    vector<Trie*> children;
};

Complexity

Time Complexity and Explanation

Insert: O(n) Search: O(n) StartWith: O(n)

Space Complexity and Explanation

Insert: O(n) Search: O(1) Startwith: O(1)

[revisegoal]

Solution

前缀树模板

Code

class Trie {
int count;
int preCount;
Trie[] children;

    public Trie() {
        count = 0;
        preCount = 0;
        children = new Trie[26];
    }

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

    public boolean search(String word) {
        Trie node = this;
        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) {
        Trie node = this;
        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;
    }
}

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

O(n)，n是字符串长度

Space

O(mn)，m是字符集大小，n是字符串长度

[zhy3213]

思路

python专属 dict记录字母，增加字段用于记录是否是word结束

代码

class Trie:

    def __init__(self):
        self.tree=dict()

    def insert(self, word: str) -> None:
        tmp=self.tree
        for i in word:
            if i in tmp:
                tmp=tmp[i]
            else:
                tmp[i]=dict()
                tmp=tmp[i]
        tmp['#']=True

    def search(self, word: str) -> bool:
        tmp=self.tree
        for i in word:
            if i not in tmp:
                return False
            tmp=tmp[i]
        return '#' in tmp

    def startsWith(self, prefix: str) -> bool:
        tmp=self.tree
        for i in prefix:
            if i not in tmp:
                return False
            tmp=tmp[i]
        return True

[muimi]

思路

每个节点有26个子节点

代码

class TrieNode{
  public char val;
  public TrieNode[] children;
  public boolean isWord;
  public TrieNode(char c) {
    val = c;
    children = new TrieNode[26];
    isWord = false;
  }
}

class Trie {
  private TrieNode root;

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

  public void insert(String word) {
    TrieNode node = root;
    for (char c : word.toCharArray()) {
      if (node.children[c - 'a'] == null) {
        node.children[c - 'a'] = new TrieNode(c);
      }
      node = node.children[c - 'a'];
    }
    node.isWord = true;
  }

  public boolean search(String word) {
    TrieNode node = root;
    for (char c : word.toCharArray()) {
      if (node.children[c - 'a'] == null) return false;
      node = node.children[c - 'a'];
    }
    return node.isWord;
  }

  public boolean startsWith(String prefix) {
    TrieNode node = root;
    for (char c : prefix.toCharArray()) {
      if (node.children[c - 'a'] == null) return false;
      node = node.children[c - 'a'];
    }
    return true;
  }
}

[BpointA]

思路

算是一种递归？

代码

class Trie:

    def __init__(self):
        self.children={}
        self.ends=False

    def insert(self, word: str) -> None:
        r=self
        for w in word:
            if w not in r.children:
                r.children[w]=Trie()
            r=r.children[w]
        r.ends=True

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

        return r.ends

    def startsWith(self, prefix: str) -> bool:
        r=self
        for w in prefix:
            if w not in r.children:
                return False
            r=r.children[w]

        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)

[ai2095]

208. Implement Trie (Prefix Tree)

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

Topics

-trie

思路

trie

代码 Python

def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = {}
        self.isWord = "$"

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        cur = self.root
        for c in word:
            if c not in cur:
                cur[c] = {}
            cur = cur[c]
        cur[self.isWord] = True

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        cur = self.root
        for c in word:
            if c not in cur:
                return False
            cur = cur[c]
        return self.isWord in cur

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

复杂度分析

Insert 时间复杂度： O(N)
空间复杂度：O(N)

search 时间复杂度： O(N)
空间复杂度：O(1)

startwith 时间复杂度： O(N)
空间复杂度：O(1)

[Daniel-Zheng]

思路

前缀树。

代码(C++)

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(N)
• 空间复杂度：O(N)

[jiahui-z]

class Trie { class TrieNode { char node; boolean isWordEnding; TrieNode[] children;

    public TrieNode() {
        this.children = new TrieNode[26];
    }

    public TrieNode(char node) {
        this.node = node;
        this.children = new TrieNode[26];
    }

    public char get() {
        return this.node;
    }
}

private TrieNode root;

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

public void insert(String word) {
    TrieNode ptr = root;
    for (int i = 0; i < word.length(); i++) { 
        char character = word.charAt(i);
        if (ptr.children[character - 'a'] == null) {
            TrieNode newNode = new TrieNode(character);
            ptr.children[character - 'a'] = newNode;
        }
        ptr = ptr.children[character - 'a'];
    }
    ptr.isWordEnding = true;
}

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

    return ptr.isWordEnding;
}

public boolean startsWith(String prefix) {
    TrieNode ptr = root;
    for (int i = 0; i < prefix.length(); i++) {
        char character = prefix.charAt(i);
        if (ptr.children[character - 'a'] == null) {
            return false;
        }
        ptr = ptr.children[character - '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); */

[asterqian]

思路

Trie

代码

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

    Trie* searchPrefix(string pre) {
        Trie* node = this;
        for (char ch: pre) {
            if (node->children[ch - 'a'] == nullptr) {
                return nullptr;
            }
            node = node->children[ch - 'a'];
        }
        return node;
    }
public:
    Trie() : children(26), isEnd(false) {}

    void insert(string word) {
        Trie* root = this;
        for (char ch: word) {
            if (root->children[ch - 'a'] == nullptr) {
                root->children[ch - 'a'] = new Trie();
            }
            root = root->children[ch - 'a'];
        }
        root->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(word.size())

空间复杂度 O(total word length * 26)

[yan0327]

思路： 采用的是多叉树的思想以及标志位isEnd 将word字符串拆成byte数组，若没有则添加一个children位，同时移动。当word遍历完时，isEnd为true 考虑到查前缀 以及 查整体都需要一个过程，因此可以整合成一个serachPrefix函数 如果没查到，返回nil，查到返回node 如果查前缀，只要不为nil 为true 。 查整体要判断不为nil且为isEnd = true

type Trie struct {
    children [26]*Trie
    isEnd bool
}

func Constructor() Trie {
    return Trie{}
}

func (this *Trie) Insert(word string)  {
    node := this
    for _,ch := range word{
        ch -= 'a'
        if node.children[ch] == nil{
            node.children[ch] = &Trie{}
        }
        node = node.children[ch]
    }
    node.isEnd = true
}

func (this *Trie) SearchPrefix(prefix string) *Trie{
    node := this
    for _,ch := range prefix{
        ch -= 'a'
        if node.children[ch] == nil{
            return nil
        }
        node = node.children[ch]
    }
    return node
}

func (this *Trie) Search(word string) bool {
    node := this.SearchPrefix(word)
    return node != nil && node.isEnd
}

func (this *Trie) StartsWith(prefix string) bool {
    return this.SearchPrefix(prefix) != nil
}

时间复杂度O（n） 空间复杂度O（ML）最坏情况是26字符串长度

[falconruo]

思路:

因为是小写字母组成，使用26个字母的数组

复杂度分析:

• 时间复杂度: O(N)，Trie()：O(1), insert()/search()/startsWith(): O(N), N为字符串长度
• 空间复杂度: O(N*M), M为字符集大小(默认为26)

代码(C++):

class TrieNode {
public:
    TrieNode* child[26];
    bool isWord;
    TrieNode():isWord(false) {
        for (auto & c : child)
            c = nullptr;
    }
};

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

    void insert(string word) {
        TrieNode* p = root;

        for (auto & ch : word) {
            int i = ch - 'a';
            if (!p->child[i])
                p->child[i] = new TrieNode();
            p = p->child[i];
        }
        p->isWord = true;
    }

    bool search(string word) {
        TrieNode* p = root;

        for (auto& ch : word) {
            int i = ch - 'a';
            if (!p->child[i]) return false;
            p = p->child[i];
        }
        return p->isWord;
    }

    bool startsWith(string prefix) {
        TrieNode* p = root;

        for (auto& ch : prefix) {
            int i = ch - 'a';
            if (!p->child[i]) return false;
            p = p->child[i];
        }

        return true;
    }
private:
    TrieNode* root;
};

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

[ZJP1483469269]

思路

字典树

代码

class Trie {
    class Node{
        boolean end;
        Node[] children = new Node[26];
    }
    Node root;
    public Trie() {
        root = new Node();
    }

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

    public boolean search(String word) {
        Node node = root;
        for(int i = 0 ;i < word.length() ;i++){
            int n = word.charAt(i) - 'a';
            if(node.children[n]==null){
                return false;
            }
            node = node.children[n];
        }
        if(node.end == true) return true;
        else return false;
    }

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

[Laurence-try]

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

[15691894985]

【Day 73】实现 Trie (前缀树

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

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(key))O(len(key))，key 是待插入(查找)的字串。

最坏情况是存储的字符没有任何前缀，建树的最坏空间复杂度是O(m*n)

[chen445]

代码

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

    def insert(self, word: str) -> None:
        currentNode=self.root
        for char in word:
            if char not in currentNode.children:
                currentNode.children[char]=TrieNode()
            currentNode=currentNode.children[char]
        currentNode.endWord=True
    def search(self, word: str) -> bool:
        currentNode=self.root
        for char in word:
            if char in currentNode.children:
                currentNode=currentNode.children[char]
            else:
                return False
        return currentNode.endWord

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

复杂度

Time:

insert O(n) word length
search O(n) word length
prefix O(n) word length

Space:

insert O(n)
search, prefix O(1)