Сложность: 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 {
var links = [TrieNode?](repeating: nil, count: 26)
var isEnd = false
func containsKey(_ ch: Character) -> Bool {
return links[Int(ch.asciiValue! - Character("a").asciiValue!)] != nil
}
func get(_ ch: Character) -> TrieNode? {
return links[Int(ch.asciiValue! - Character("a").asciiValue!)]
}
func put(_ ch: Character, _ node: TrieNode) {
links[Int(ch.asciiValue! - Character("a").asciiValue!)] = node
}
func setEnd() {
isEnd = true
}
}
class Trie {
private var root = TrieNode()
func insert(_ word: String) {
var node = root
for ch in word {
if !node.containsKey(ch) {
node.put(ch, TrieNode())
}
node = node.get(ch)!
}
node.setEnd()
}
private func searchPrefix(_ word: String) -> TrieNode? {
var node = root
for ch in word {
if node.containsKey(ch) {
node = node.get(ch)!
} else {
return nil
}
}
return node
}
func search(_ word: String) -> Bool {
if let node = searchPrefix(word) {
return node.isEnd
}
return false
}
func startsWith(_ prefix: String) -> Bool {
return searchPrefix(prefix) != nil
}
}Ставь 👍 и забирай 📚 Базу знаний