← Static tasks

208. Implement Trie (Prefix Tree)

leetcode medium

#csharp#design#graph#hash-table#leetcode#medium#prefix-sum#search#string#tree#trie

Task

Trie (произносится как "трай") или префиксное дерево — это древовидная структура данных, используемая для эффективного хранения и поиска ключей в наборе строк. Существует множество применений этой структуры данных, таких как автозаполнение и проверка орфографии.

Реализуйте класс Trie:

Trie() инициализирует объект trie.

void insert(String word) вставляет строку word в trie.

boolean search(String word) возвращает true, если строка word есть в trie (то есть была вставлена ранее), и false в противном случае.

boolean startsWith(String prefix) возвращает true, если есть ранее вставленная строка word, которая имеет префикс prefix, и false в противном случае.

Пример:

Input

["Trie", "insert", "search", "search", "startsWith", "insert", "search"]

[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

Output

[null, null, true, false, true, null, true]

Explanation

Trie trie = new Trie();

trie.insert("apple");

trie.search("apple"); // return True

trie.search("app"); // return False

trie.startsWith("app"); // return True

trie.insert("app");

trie.search("app"); // return True

C# solution

matched/original
public class TrieNode {
    private TrieNode[] links = new TrieNode[26];
    private bool isEnd;
    public bool ContainsKey(char ch) {
        return links[ch - 'a'] != null;
    }
    public TrieNode Get(char ch) {
        return links[ch - 'a'];
    }
    public void Put(char ch, TrieNode node) {
        links[ch - 'a'] = node;
    }
    public void SetEnd() {
        isEnd = true;
    }
    public bool IsEnd() {
        return isEnd;
    }
}
public class Trie {
    private TrieNode root = new TrieNode();
    public void Insert(string word) {
        TrieNode node = root;
        foreach (char ch in word) {
            if (!node.ContainsKey(ch)) {
                node.Put(ch, new TrieNode());
            }
            node = node.Get(ch);
        }
        node.SetEnd();
    }
    private TrieNode SearchPrefix(string word) {
        TrieNode node = root;
        foreach (char ch in word) {
            if (node.ContainsKey(ch)) {
                node = node.Get(ch);
            } else {
                return null;
            }
        }
        return node;
    }
    public bool Search(string word) {
        TrieNode node = SearchPrefix(word);
        return node != null && node.IsEnd();
    }
    public bool StartsWith(string prefix) {
        return SearchPrefix(prefix) != null;
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class TrieNode {
    private TrieNode[] links = new TrieNode[26];
    private bool isEnd;
    public bool ContainsKey(char ch) {
        return links[ch - 'a'] != null;
    }
    public TrieNode Get(char ch) {
        return links[ch - 'a'];
    }
    public void Put(char ch, TrieNode node) {
        links[ch - 'a'] = node;
    }
    public void SetEnd() {
        isEnd = true;
    }
    public bool IsEnd() {
        return isEnd;
    }
}
public class Trie {
    private TrieNode root = new TrieNode();
    public void Insert(string word) {
        TrieNode node = root;
        foreach (char ch in word) {
            if (!node.count(ch)) {
                node.Put(ch, new TrieNode());
            }
            node = node.Get(ch);
        }
        node.SetEnd();
    }
    private TrieNode SearchPrefix(string word) {
        TrieNode node = root;
        foreach (char ch in word) {
            if (node.count(ch)) {
                node = node.Get(ch);
            } else {
                return null;
            }
        }
        return node;
    }
    public bool Search(string word) {
        TrieNode node = SearchPrefix(word);
        return node != null && node.IsEnd();
    }
    public bool StartsWith(string prefix) {
        return SearchPrefix(prefix) != null;
    }
}

Java solution

matched/original
class TrieNode {
    private TrieNode[] links = new TrieNode[26];
    private boolean isEnd;

    public boolean containsKey(char ch) {
        return links[ch - 'a'] != null;
    }

    public TrieNode get(char ch) {
        return links[ch - 'a'];
    }

    public void put(char ch, TrieNode node) {
        links[ch - 'a'] = node;
    }

    public void setEnd() {
        isEnd = true;
    }

    public boolean isEnd() {
        return isEnd;
    }
}

class Trie {
    private TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            if (!node.containsKey(ch)) {
                node.put(ch, new TrieNode());
            }
            node = node.get(ch);
        }
        node.setEnd();
    }

    private TrieNode searchPrefix(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            if (node.containsKey(ch)) {
                node = node.get(ch);
            } else {
                return null;
            }
        }
        return node;
    }

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

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

JavaScript solution

matched/original
class TrieNode {
    constructor() {
        this.links = new Array(26).fill(null);
        this.isEnd = false;
    }

    containsKey(ch) {
        return this.links[ch.charCodeAt(0) - 'a'.charCodeAt(0)] !== null;
    }

    get(ch) {
        return this.links[ch.charCodeAt(0) - 'a'.charCodeAt(0)];
    }

    put(ch, node) {
        this.links[ch.charCodeAt(0) - 'a'.charCodeAt(0)] = node;
    }

    setEnd() {
        this.isEnd = true;
    }

    isEndNode() {
        return this.isEnd;
    }
}

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

    insert(word) {
        let node = this.root;
        for (let ch of word) {
            if (!node.containsKey(ch)) {
                node.put(ch, new TrieNode());
            }
            node = node.get(ch);
        }
        node.setEnd();
    }

    searchPrefix(word) {
        let node = this.root;
        for (let ch of word) {
            if (node.containsKey(ch)) {
                node = node.get(ch);
            } else {
                return null;
            }
        }
        return node;
    }

    search(word) {
        let node = this.searchPrefix(word);
        return node !== null && node.isEndNode();
    }

    startsWith(prefix) {
        return this.searchPrefix(prefix) !== null;
    }
}

Python solution

matched/original
class TrieNode:
    def __init__(self):
        self.links = [None] * 26
        self.is_end = False

    def contains_key(self, ch):
        return self.links[ord(ch) - ord('a')] is not None

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

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

    def set_end(self):
        self.is_end = True

    def is_end(self):
        return self.is_end

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

    def insert(self, word):
        node = self.root
        for ch in word:
            if not node.contains_key(ch):
                node.put(ch, TrieNode())
            node = node.get(ch)
        node.set_end()

    def search_prefix(self, word):
        node = self.root
        for ch in word:
            if node.contains_key(ch):
                node = node.get(ch)
            else:
                return None
        return node

    def search(self, word):
        node = self.search_prefix(word)
        return node is not None and node.is_end()

    def starts_with(self, prefix):
        return self.search_prefix(prefix) is not None

Go solution

matched/original
package main

type TrieNode struct {
    links [26]*TrieNode
    isEnd bool
}

func (node *TrieNode) containsKey(ch byte) bool {
    return node.links[ch-'a'] != nil
}

func (node *TrieNode) get(ch byte) *TrieNode {
    return node.links[ch-'a']
}

func (node *TrieNode) put(ch byte, newNode *TrieNode) {
    node.links[ch-'a'] = newNode
}

func (node *TrieNode) setEnd() {
    node.isEnd = true
}

func (node *TrieNode) isEndNode() bool {
    return node.isEnd
}

type Trie struct {
    root *TrieNode
}

func Constructor() Trie {
    return Trie{root: &TrieNode{}}
}

func (this *Trie) Insert(word string) {
    node := this.root
    for i := 0; i < len(word); i++ {
        ch := word[i]
        if !node.containsKey(ch) {
            node.put(ch, &TrieNode{})
        }
        node = node.get(ch)
    }
    node.setEnd()
}

func (this *Trie) searchPrefix(word string) *TrieNode {
    node := this.root
    for i := 0; i < len(word); i++ {
        ch := word[i]
        if node.containsKey(ch) {
            node = node.get(ch)
        } else {
            return nil
        }
    }
    return node
}

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

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

Explanation

Algorithm

1️⃣

Инициализация и вставка в Trie:

Создайте класс Trie, который включает в себя метод insert(String word) для добавления строк в Trie.

Метод insert инициализирует текущий узел как корень и проходит по каждому символу строки. Если текущий узел не содержит символа, создайте новый узел. В конце отметьте последний узел как конец слова.

2️⃣

Поиск строки в Trie:

Создайте метод search(String word), который использует вспомогательный метод searchPrefix(String word) для поиска строки или префикса в Trie.

В методе searchPrefix начните с корневого узла и для каждого символа строки перемещайтесь к следующему узлу. Если на каком-то этапе узел не содержит текущего символа, верните null. В противном случае, в конце строки верните текущий узел.

3️⃣

Проверка наличия префикса в Trie:

Создайте метод startsWith(String prefix), который также использует метод searchPrefix(String prefix).

Метод startsWith вызывает searchPrefix и возвращает true, если возвращаемый узел не равен null, что указывает на наличие префикса в Trie.

😎