Ежедневный вызов Leetcode [17 марта 2023 г.]
trie (произносится как попробуй) или префиксное дерево — это древовидная структура данных, используемая для эффективного хранения и извлечения ключей в наборе строковых данных. Существуют различные приложения этой структуры данных, такие как автозаполнение и проверка орфографии.
Реализуйте класс Trie:
Trie()Инициализирует объект trie.void insert(String word)Вставляет строкуwordв дерево.boolean search(String word)Возвращаетtrue, если строкаwordнаходится в дереве (т. е. была вставлена ранее), иfalseв противном случае.boolean startsWith(String prefix)Возвращаетtrue, если имеется ранее вставленная строкаwordс префиксомprefix, иfalseв противном случае.
Пример 1:
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
Давайте посмотрим на диаграмму ниже, как работает Trie.
TrieNode состоит из массива TrieNode для хранения ссылки на следующий TrieNode и одного логического флага, чтобы узнать, является ли это концом слова или нет.
class TrieNode {
TrieNode[] childrens;
boolean endOfWord;
TrieNode() {
childrens = new TrieNode[26];
endOfWord = false;
}
}
Вставить слово
Мы просматриваем букву слова одну за другой и для этого символа добавляем новый TrieNode, который показывает, что он является частью слова, и мы переходим к этому вновь созданному TrieNode, помните, что нам не нужно создавать, если он уже существует.
См. диаграмму ниже, как работает Trie в случае Insert.
public void insert(String word) {
TrieNode curr = root;
for(char x: word.toCharArray()) {
int ind = x-'a';
if(curr.childrens[ind] == null)
curr.childrens[ind] = new TrieNode();
curr = curr.childrens[ind];
}
curr.endOfWord = true;
}
Поиск слова
Поиск и вставка почти аналогичны, мы просто перебираем символы слова, и если мы не находим TrieNode для символа, мы просто возвращаем false. (Вы помните, что в случае Insert мы добавили новый TrieNode в этот момент.)
public boolean search(String word) {
TrieNode curr = root;
for(char x: word.toCharArray()) {
int ind = x - 'a';
if(curr.childrens[ind] == null) return false;
curr = curr.childrens[ind];
}
return curr.endOfWord;
}
Проверить слово префикса
Search и Prefix почти аналогичны, вместо того, чтобы проверять, является ли это концом слова, мы возвращаем true.
Потому что, если мы ищем «Приложение», у нас должно быть слово «Приложение», но если мы проверим префиксы для «Приложения», то «Приложение», «Apple» и «Приложение» будут действительными и вернут true.
public boolean startsWith(String prefix) {
TrieNode curr = root;
for(char x: prefix.toCharArray()) {
int ind = x - 'a';
if(curr.childrens[ind] == null) return false;
curr = curr.childrens[ind];
}
return true;
}
Теперь подведите итог, посмотрите полный код -
class TrieNode {
TrieNode[] childrens;
boolean endOfWord;
TrieNode() {
childrens = new TrieNode[26];
endOfWord = false;
}
}
class Trie {
static TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode curr = root;
for(char x: word.toCharArray()) {
int ind = x-'a';
if(curr.childrens[ind] == null)
curr.childrens[ind] = new TrieNode();
curr = curr.childrens[ind];
}
curr.endOfWord = true;
}
public boolean search(String word) {
TrieNode curr = root;
for(char x: word.toCharArray()) {
int ind = x - 'a';
if(curr.childrens[ind] == null) return false;
curr = curr.childrens[ind];
}
return curr.endOfWord;
}
public boolean startsWith(String prefix) {
TrieNode curr = root;
for(char x: prefix.toCharArray()) {
int ind = x - 'a';
if(curr.childrens[ind] == null) return false;
curr = curr.childrens[ind];
}
return true;
}
}
увидеть результаты
Потом я подумал, что код поиска и префикса можно объединить, потому что у них много общего.
Посмотреть новый код -
class TrieNode {
TrieNode[] childrens;
boolean endOfWord;
TrieNode() {
childrens = new TrieNode[26];
endOfWord = false;
}
}
class Trie {
static TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode curr = root;
for(char x: word.toCharArray()) {
int ind = x-'a';
if(curr.childrens[ind] == null)
curr.childrens[ind] = new TrieNode();
curr = curr.childrens[ind];
}
curr.endOfWord = true;
}
private boolean searchCommon(String word, Boolean prefixSearch) {
TrieNode curr = root;
for(char x: word.toCharArray()) {
int ind = x - 'a';
if(curr.childrens[ind] == null) return false;
curr = curr.childrens[ind];
}
return prefixSearch || curr.endOfWord;
}
public boolean search(String word) {
return searchCommon(word, false);
}
public boolean startsWith(String prefix) {
return searchCommon(prefix, true);
}
}
Но опять же мне приходит в голову, что зачем выделять лишнее место под массив, можно использовать HashMap вместо массива.
Помните, что это будет просто оптимизация памяти, а не оптимизация времени, потому что мы можем получить элемент из массива для индекса с временной сложностью O(1).
увидеть код с использованием HashMap -
class TrieNode {
Map<Character, TrieNode> childrens;
boolean endOfWord;
TrieNode() {
childrens = new HashMap<>();
endOfWord = false;
}
}
class Trie {
static TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode curr = root;
for(char x: word.toCharArray()) {
if(!curr.childrens.containsKey(x))
curr.childrens.put(x, new TrieNode());
curr = curr.childrens.get(x);
}
curr.endOfWord = true;
}
private boolean searchCommon(String word, Boolean prefixSearch) {
TrieNode curr = root;
for(char x: word.toCharArray()) {
if(!curr.childrens.containsKey(x)) return false;
curr = curr.childrens.get(x);
}
return prefixSearch || curr.endOfWord;
}
public boolean search(String word) {
return searchCommon(word, false);
}
public boolean startsWith(String prefix) {
return searchCommon(prefix, true);
}
}
Вот и все !!!
Похожие вопросы:
Дизайн структуры данных «Добавление и поиск слов — LeetCode
Можете ли вы решить этот реальный вопрос на собеседовании? Разработайте структуру данных для добавления и поиска слов. Разработайте структуру данных, которая…leetcode.com»
Спасибо вам всем !!!
