Задача: 208. Implement Trie (Prefix Tree)
Сложность: medium

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

👨‍💻 Алгоритм:

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.

😎 Решение:

class TrieNode {
    private $links;
    private $isEnd;

    public function __construct() {
        $this->links = array_fill(0, 26, null);
        $this->isEnd = false;
    }

    public function containsKey($ch) {
        return $this->links[ord($ch) - ord('a')] !== null;
    }

    public function get($ch) {
        return $this->links[ord($ch) - ord('a')];
    }

    public function put($ch, $node) {
        $this->links[ord($ch) - ord('a')] = $node;
    }

    public function setEnd() {
        $this->isEnd = true;
    }

    public function isEndNode() {
        return $this->isEnd;
    }
}

class Trie {
    private $root;

    public function __construct() {
        $this->root = new TrieNode();
    }

    public function insert($word) {
        $node = $this->root;
        for ($i = 0; $i < strlen($word); $i++) {
            $ch = $word[$i];
            if (!$node->containsKey($ch)) {
                $node->put($ch, new TrieNode());
            }
            $node = $node->get($ch);
        }
        $node->setEnd();
    }

    private function searchPrefix($word) {
        $node = $this->root;
        for ($i = 0; $i < strlen($word); $i++) {
            $ch = $word[$i];
            if ($node->containsKey($ch)) {
                $node = $node->get($ch);
            } else {
                return null;
            }
        }
        return $node;
    }

    public function search($word) {
        $node = $this->searchPrefix($word);
        return $node !== null && $node->isEndNode();
    }

    public function startsWith($prefix) {
        return $this->searchPrefix($prefix) !== null;
    }
}

Ставь 👍 и забирай 📚 Базу знаний