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

[yetfan]

思路 感觉写类要比写算法省事多了=。=

代码

class TrieNode(object):
    def __init__(self):
        self.children = {}
        self.end = 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.end = True

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

    def search(self, word: str) -> bool:
        node = self.search_prefix(word)
        if node and node.end:
            return True
        else:
            return False

    def startsWith(self, prefix: str) -> bool:
        node = self.search_prefix(prefix)
        if node:
            return True
        else:
            return False

[ZJP1483469269]

class Trie:

    def __init__(self):
        self.children = [None] * 26
        self.end = 0

    def insert(self, word: str) -> None:
        node = self
        for c in word:
            idx = ord(c) - ord('a')
            if not node.children[idx]:
                node.children[idx] = Trie()
            node = node.children[idx]
        node.end = 1

    def search(self, word: str) -> bool:
        node = self
        for c in word:
            idx = ord(c) - ord('a')
            if node.children[idx]:
                node = node.children[idx]
            else:
                return False
        if node.end:
            return True
        else:
            return False

    def startsWith(self, prefix: str) -> bool:
        node = self
        for c in prefix:
            idx = ord(c) - ord('a')
            if node.children[idx]:
                node = node.children[idx]
            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)

[zwx0641]

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

void insert(string word) {
    Trie *node = this;
    for (auto& 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->searchPre(word);
    return node != nullptr && node->isEnd;
}

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

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

Trie* searchPre(string word) {
    Trie* node = this;
    for (auto& ch : word) {
        ch -= 'a';
        if (node->children[ch] == nullptr) {
            return nullptr;
        }
        node = node->children[ch];
    }
    return node;
}

};

/**

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

[rzhao010]

class Node {
    boolean isEnd;
    Node[] son = new Node[26];
    Node() {
        isEnd = false;
        for (int i = 0; i < 26; i++) {
            son[i] = null;
        }
    }
}
class Trie {
    Node root;

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

    public void insert(String word) {
        Node p = root;
        for (int i = 0; i < word.length(); i++) {
            int u = word.charAt(i) - 'a';
            if (p.son[u] == null) {
                p.son[u] = new Node();
                p = p.son[u];
            }
        }
        p.isEnd = true;
    }

    public boolean search(String word) {
        Node p = root;
        for (int i = 0; i < word.length(); i++) {
            int u = word.charAt(i) - 'a';
            if (p.son[u] == null) {
                return false;
            }
            p = p.son[u];
        }
        return p.isEnd;
    }

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

Complexity Time: O(n) Space: O(n) n is the length of input string

[feifan-bai]

思路 1.回溯

代码

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

[yijing-wu]

class Trie {
    class TrieNode {
        boolean end;
        TrieNode[] tns = new TrieNode[26];
    }

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

    public void insert(String s) {
        TrieNode p = root;
        for(int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (p.tns[u] == null) p.tns[u] = new TrieNode();
            p = p.tns[u]; 
        }
        p.end = true;
    }

    public boolean search(String s) {
        TrieNode p = root;
        for(int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (p.tns[u] == null) return false;
            p = p.tns[u]; 
        }
        return p.end;
    }

    public boolean startsWith(String s) {
        TrieNode p = root;
        for(int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (p.tns[u] == null) return false;
            p = p.tns[u]; 
        }
        return true;
    }
}

[CoreJa]

思路

前缀树：实现前缀树，写个基础板子。前缀树其实就是一个多叉树，方便快速查找前缀。假设关键词长度为n，则插入和搜索的复杂度都是$O(n)$。

代码

# 前缀树：实现前缀树，写个基础板子。前缀树其实就是一个多叉树，方便快速查找前缀。假设关键词长度为n，则插入和搜索的复杂度都是
# $O(n)$。
class Trie:
    def __init__(self):
        self.root = {}

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

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

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

[LinnSky]

代码

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

[wangzehan123]

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

[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

search: time O(N), space O(1) insert: time O(N), space O(N)

[QinhaoChang]

class Node:

def __init__(self):
    self.word = None
    self.children = {}

class Trie:

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

def insert(self, word: str) -> None:    
    cur = self.root
    for char in word:
        if char not in cur.children:
            cur.children[char] = Node()
        cur = cur.children[char]
    cur.word = word

def get_node(self, string):
    cur = self.root
    for char in string:
        if char not in cur.children:
            return None
        cur = cur.children[char]
    return cur

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

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

[Alexno1no2]

class Trie:

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

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

    def search(self, word: str) -> bool:
        return self.startsWith(word + '#')

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

[Tesla-1i]

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

[yan0327]

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
}

[xuhzyy]

class Node:
    def __init__(self):
        self.pre = 0
        self.cnt = 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.pre += 1
        node.cnt += 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.cnt > 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

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

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

[haixiaolu]

class Trie:

    def __init__(self):
        self.children = [None] * 26
        self.isEnd = False

    def searchPrefix(self, prefix):
        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 

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

[hdyhdy]

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

func Constructor() Trie {
    return Trie{}
}

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

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

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

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

[ZacheryCao]

Idea

Trie

Code:

class Trie:

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

    def insert(self, word: str) -> None:
        cur = self.root;
        for i in word:
            cur = cur.setdefault(i, {})
        cur["#"] = False;

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

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

[Arya-03]

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

[charlestang]

思路

字典树实现

代码

class Trie:

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

    def insert(self, word: str) -> None:
        n = len(word)

        d = self.d
        for k, c in enumerate(word):
            if c not in d:
                d[c] = {}
            d = d[c]
            if k == n - 1:
                d['end'] = True

    def search(self, word: str) -> bool:
        n = len(word)
        d = self.d
        for k, c in enumerate(word):
            if c not in d:
                return False
            d = d[c]
            if k == n - 1:
                return 'end' in d
        return False

    def startsWith(self, prefix: str) -> bool:
        n = len(prefix)
        d = self.d

        for c in prefix:
            if c in d:
                d = d[c]
            else:
                return False
        return True

[Myleswork]

思路

主要是节点的设计，数组表示字母，isend表示当前节点是否为单词末尾

代码

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

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

    void insert(string word) {
        trienode *p = root;
        for(char w:word){
            int index = w-'a';
            if(!p->child[index]) p->child[index] = new trienode();
            p=p->child[index];
        }
        p->isend = true;
    }

    bool search(string word) {
        trienode *p=root;
        for(char w:word){
            int index = w-'a';
            if(!p->child[index]) return false;
            p=p->child[index];
        }
        return p->isend;
    }

    bool startsWith(string prefix) {
        trienode *p=root;
        for(char w:prefix){
            int index = w-'a';
            if(!p->child[index]) return false;
            p=p->child[index];
        }
        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(len)

空间复杂度：不好说

[LannyX]

代码

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)

[ivangin]

code:

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

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

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

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

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

[callmeerika]

思路

前缀树

代码

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

Trie.prototype.insert = function (word) {
  let node = this.children;
  for (let i of word) {
    if (!node[i]) node[i] = { count: 0, preCount: 0 };
    node = node[i];
    node.preCount += 1;
  }
  node.count += 1;
};

Trie.prototype.search = function (word) {
  let node = this.children;
  for (let i of word) {
    if (!node[i]) return false;
    node = node[i];
  }
  return node.count > 0;
};

Trie.prototype.startsWith = function (prefix) {
  let node = this.children;
  for (let i of prefix) {
    if (!node[i]) return false;
    node = node[i];
  }
  return true;
};

复杂度

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

[JudyZhou95]

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

class Trie:

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

    def insert(self, word: str) -> None:
        p = self.root

        for c in word:
            if c not in p.children:
                p.children[c] = TrieNode()
            p = p.children[c]

        p.isWord = True

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

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

[1149004121]

208. 实现 Trie (前缀树)

思路

前缀树。

代码

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

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

/** 
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
    let node = this.children;
    for(let char of word){
        if(!node[char]) return false;
        node = node[char];
    };
    return node.isEnd !== undefined;
};

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

复杂度分析

• 时间复杂度：O(N )。
• 空间复杂度：O(N * M )。

[zhangzz2015]

思路

• 标准trie 数据结构的模板，时间复杂度为O(n)，空间复杂度为O(n*m)，

关键点

代码

• 语言支持：C++

C++ Code:

struct node
{
vector<node*>  child; 
bool isWord;     
    node()
    {
        child.resize(26,NULL); 
        isWord=false; 
    }

}; 

class Trie {
public:
    node* root; 

    Trie() {

        root = new node();         
    }

    void insert(string word) {
        node* current = root; 
        for(auto& s: word)
        {
            int index = s - 'a'; 
            if(current->child[index]==NULL)
            {
                current->child[index] = new node(); 
            }
            current = current->child[index]; 
        }

        current->isWord = true;                 
    }

    bool search(string word) {
        node* current = root; 
        for(auto& s: word)
        {
            int index = s - 'a'; 
            if(current->child[index]==NULL)
                return false; 
            current = current->child[index];             
        }
        return current->isWord;         
    }

    bool startsWith(string prefix) {

        node* current = root; 
        for(auto & s: prefix)
        {
            int index = s - 'a'; 
            if(current->child[index]==NULL)
                return false; 
            current = current->child[index]; 
        }
        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);
 */

[zol013]

class Trie:

    def __init__(self):
        self.children = [None] * 26
        self.isEnd = False

    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
        for ch in word:
            ch = ord(ch) - ord('a')
            if not node.children[ch]:
                return False
            node = node.children[ch]

        return node.isEnd == True

    def startsWith(self, prefix: str) -> bool:
        node = self

        for ch in prefix:
            ch = ord(ch) - ord('a')
            if not node.children[ch]:
                return False
            node = node.children[ch]

        return True

[C2tr]

class Trie:

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

def insert(self, word: str) -> None:
    """
    Inserts a word into the trie.
    """
    tree = self.lookup
    for a in word:
        if a not in tree:
            tree[a] = {}
        tree = tree[a]
    # 单词结束标志
    tree["#"] = "#"

def search(self, word: str) -> bool:
    """
    Returns if the word is in the trie.
    """
    tree = self.lookup
    for a in word:
        if a not in tree:
            return False
        tree = tree[a]
    if "#" in tree:
        return True
    return False

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

[xqmmy]

class Node: def init(self): self.child = [None for _ in range(26)] self.isEnd = False

def contain_key(self,ch):
    return self.child[ord(ch)-ord('a')]

def get(self,ch):
    return self.child[ord(ch)-ord('a')]

def put(self,ch):
    self.child[ord(ch)-ord('a')] = Node()

class Trie:

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

def insert(self, word: str) -> None:
    """
    Inserts a word into the trie.
    """
    p = self.root
    for i in word:
        if not p.contain_key(i):
            p.put(i)
        p = p.get(i)
    p.isEnd = True

def search(self, word: str) -> bool:
    """
    Returns if the word is in the trie.
    """
    p = self.root
    for i in word:
        if not p.contain_key(i):
            return False
        else:
            p = p.get(i)
    return p.isEnd

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

[jiaqiliu37]

class Trie:

    def __init__(self):
        self.children = [None]*26
        self.isEnd = False

    def insert(self, word: str) -> None:
        node = self
        for char in word:
            idx = ord(char) - ord('a')
            if node.children[idx] == None:
                node.children[idx] = Trie()
            node = node.children[idx]

        node.isEnd = True

    def search(self, word: str) -> bool:
        node = self
        for char in word:
            idx = ord(char) - ord('a')
            if node.children[idx] == None:
                return False
            node = node.children[idx]

        return node.isEnd

    def startsWith(self, prefix: str) -> bool:
        node = self
        for char in prefix:
            idx = ord(char) - ord('a')
            if node.children[idx] == None:
                return False
            node = node.children[idx]

        return True

[falconruo]

思路: 字典树

代码(C++):

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

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;

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

    /** Returns if the word is in the trie. */
    bool search(string word) {
        TrieNode* p = root;

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

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        TrieNode* p = root;

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

private:
    TrieNode* root;
};

[KennethAlgol]

class Trie {
    class TrieNode {
        boolean end;
        TrieNode[] tns = new TrieNode[26];
    }

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

    public void insert(String s) {
        TrieNode p = root;
        for(int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (p.tns[u] == null) p.tns[u] = new TrieNode();
            p = p.tns[u]; 
        }
        p.end = true;
    }

    public boolean search(String s) {
        TrieNode p = root;
        for(int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (p.tns[u] == null) return false;
            p = p.tns[u]; 
        }
        return p.end;
    }

    public boolean startsWith(String s) {
        TrieNode p = root;
        for(int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (p.tns[u] == null) return false;
            p = p.tns[u]; 
        }
        return true;
    }
}

[biscuit279]

思路

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

    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):
        """
        :type word: str
        :rtype: 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):
        """
        :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):
        """
        :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

# 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) 空间复杂度：O(字符集大小*总字符数)

[Aobasyp]

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

时间复杂度：创建 Trie:O(1), 其余操作为 O(n)

[declan92]

java

class Trie {
    TrieNode root;

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

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

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

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

class TrieNode {
    public TrieNode[] children;
    public int count;
    public int preCount;

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

时间:插入,查询$O(len(key))$
空间:$O(m*n)$,m为字符集大小,n为word数组平均字符长度

[last-Battle]

struct node
{
vector<node*>  child; 
bool isWord;     
node() : isWord(false)
{
    child.resize(26,NULL);  
}
}; 

class Trie {
public:
    node* root; 

    Trie() {

        root = new node();         
    }

    void insert(string word) {
        node* current = root; 
        for(auto& s: word)
        {
            int index = s - 'a'; 
            if(current->child[index]==NULL)
            {
                current->child[index] = new node(); 
            }
            current = current->child[index]; 
        }

        current->isWord = true;                 
    }

    bool search(string word) {
        node* current = root; 
        for(auto& s: word)
        {
            int index = s - 'a'; 
            if(current->child[index]==NULL)
                return false; 
            current = current->child[index];             
        }
        return current->isWord;         
    }

    bool startsWith(string prefix) {

        node* current = root; 
        for(auto & s: prefix)
        {
            int index = s - 'a'; 
            if(current->child[index]==NULL)
                return false; 
            current = current->child[index]; 
        }
        return true;                     
    }
};

[guangsizhongbin]

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

func Constructor() Trie { return Trie{} }

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

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

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

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

[alongchong]

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

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

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

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

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

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

[demo410]

class Trie {
    TrieNode root;

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

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

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

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

class TrieNode {
    public TrieNode[] children;
    public int count;
    public int preCount;

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

[CodingProgrammer]

思路

没啥，就背呗

代码

class Trie {

    class TrieNode {
        boolean isEnd;
        TrieNode[] children;

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

    TrieNode root;

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

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

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

        return curr.isEnd;
    }

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

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

[ChenJingjing85]

class Node:
    def __init__(self) -> None:
        self.children = {}
        self.isEnd = False #是否是单词结尾
        # self.preCount = 0 #前缀长度，可用于判断是否是dancijiewei

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

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

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

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

[shamworld]

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

/** 
 * @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);
};
Trie.prototype.searchPrefix = function(prefix) {
    let node = this.children;
    for (const ch of prefix) {
        if (!node[ch]) {
            return false;
        }
        node = node[ch];
    }
    return node;
}

[MissNanLan]

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

Trie.prototype.insert = function (word) {
  let node = this.root;
  for (const c of word) {
    if (!node[c]) node[c] = {};
    node = node[c];
  }
  node.isEnd = true;
};

Trie.prototype.search = function (word, node = this.root) {
  for (const c of word) {
    if (!node[c]) return false;
    node = node[c];
  }

  return node.isEnd === true;
};

Trie.prototype.startsWith = function (prefix, node = this.root) {
  for (const c of prefix) {
    if (!node[c]) return false;
    node = node[c];
  }
  return true;
};

[dahaiyidi]

Problem

208. 实现 Trie (前缀树)

++

难度中等1065

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

请你实现 Trie 类：

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

---

Note

• 由字符串搭建一个树

---

Complexity

• 时间O：
• 空间O：

---

Python

C++

class Trie {
private:
    bool isEnd;
    Trie* next[26];
public:
    Trie() {
        isEnd = 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->isEnd = 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->isEnd;
    }

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

From : https://github.com/dahaiyidi/awsome-leetcode

[pwqgithub-cqu]

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

}

[Hacker90]

思路 感觉写类要比写算法省事多了=。=

代码

class TrieNode(object): def init(self): self.children = {} self.end = 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.end = True

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

def search(self, word: str) -> bool:
    node = self.search_prefix(word)
    if node and node.end:
        return True
    else:
        return False

def startsWith(self, prefix: str) -> bool:
    node = self.search_prefix(prefix)
    if node:
        return True
    else:
        return False

[fornobugworld]

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

[machuangmr]

代码

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

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

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

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

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

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