Выпуск # 642 на летекоде: поиск дизайна AutoComplete System
Описание темы
Разработайте систему автозаполнения для поисковых систем. Пользователь может ввести предложение (как минимум одно слово, заканчивающееся специальным символом «#»). Для каждого символа, кроме «#», вам необходимо вернуть 3 самых популярных предложения с тем же префиксом, что и уже введенная часть предложения. Конкретные правила заключаются в следующем:
Популярность предложения определяется количеством раз, когда пользователь вводит одно и то же предложение. Верхние 3 верхних предложения должны быть отсортированы по популярности (первое — самое горячее). Если несколько предложений имеют одинаковую популярность, необходимо использовать порядок кода ascii (меньшее отображается первым). Если популярных предложений меньше 3, то верните как можно больше. Когда ввод является специальным символом, это означает конец предложения, и в этом случае вам нужно вернуть пустой список. Ваша задача заключается в реализации следующих функций:
Конструктор:
AutocompleteSystem (предложение String [], int [] times): это конструктор. На входе исторические данные. Предложения — это массив строк, состоящий из ранее введенных предложений. Times — это соответствующее количество раз, когда предложение вводится. Ваша система должна регистрировать эти исторические данные.
Теперь пользователь хочет ввести новое предложение. Следующая функция предоставит следующий символ пользовательского типа:
Ввод списка (char c): ввод c — это следующий символ, введенный пользователем. Символы могут быть только строчными буквами («от a» до «z»), пробелами («») или специальными символами («#»). Также ранее введенные предложения должны быть зафиксированы в системе. На выходе будут 3 лучших исторических популярных предложения с тем же префиксом, что и уже введенная часть предложения.
пример: Действие: AutocompleteSystem(["я люблю тебя", "остров", "железный человек", "я люблю литкод"], [5,3,2,2]) Система отследила следующие предложения и их соответствующее время:
"i love you" : 5 times "island" : 3 times "ironman" : 2 times "i love leetcode" : 2 times
Теперь пользователь начинает другой поиск:
Действие: ввод("я") Вывод: ["я люблю тебя", "остров", "я люблю литкод"] объяснять: Четыре предложения с приставкой «i». Среди них «железный человек» и «я люблю литкод» имеют одинаковую популярность. Поскольку код ASCII " " равен 32, а код ASCII "r" равен 114, то "i love leetcode" должен предшествовать "ironman". Кроме того, нам нужно вывести только 3 верхних предложения, поэтому «железный человек» будет проигнорирован.
Действие: ввод(' ') Вывод: ["я люблю тебя", "я люблю литкод"] объяснять: Только в двух предложениях есть приставка «i».
Действие: ввод('а') вывод: [] объяснять: Нет предложений с префиксом «i a».
Действие: введите ("#") вывод: [] объяснять: После того, как пользователь завершает ввод, предложение «ia» сохраняется в системе как историческое предложение. Следующий ввод будет считаться новым поиском.
Уведомление:
Набранные предложения всегда начинаются с буквы, заканчиваются знаком «#» и имеют только один пробел между двумя словами. Для поиска будет не более 100 полных предложений. Длина каждого предложения, включая исторические данные, не должна превышать 100 предложений. При написании тестовых случаев используйте двойные кавычки вместо одинарных, даже для ввода символов. Не забудьте сбросить переменные класса, объявленные в классе AutocompleteSystem, потому что статические переменные/классы сохраняются в нескольких тестовых примерах. Нажмите здесь, чтобы узнать подробности.
Значение темы:
Чтобы спроектировать систему автозаполнения поиска, она должна включать следующие два метода:
Метод строительства:
AutocompleteSystem(String[] Offerings, int[] times): Введите предложения предложений и время их появления.
Метод ввода:
Ввод списка (char c): введите символ c, который может состоять из 26 строчных букв алфавита, а также пробела до '#' в конце. Возвращает префикс входного символа, соответствующий наибольшей частоте до трех предложений, отсортированных по лексикографической равной частоте.
Анализ идей:
Основная точка: Trie (словарное дерево)
Используйте дерево словаря, чтобы записать все появившиеся наборы предложений, и используйте словарь, чтобы сохранить количество вхождений каждого предложения.
Идеи решения проблем
Требование к заголовку состоит в том, чтобы завершенные предложения располагались в соответствии с частотой предыдущих вхождений, при этом наиболее часто встречающиеся были вверху, а если частота одинакова, они будут отображаться в алфавитном порядке.
Частота Этот тип требований легко представить в виде точек знаний, таких как куча, приоритетная очередь, дерево, карта и т. д., которые включают словарь и дерево, и должны быть решены с использованием словарного дерева.
Trie настроен таким образом, что первая конфигурация и метод вставки trieNode, готовая структура класса trieNode, затем корневой узел древовидной структуры.
Поскольку нам нужно вводить символы за раз, мы можем использовать приватный Node: curNode для отслеживания текущего узла.
curNode инициализируется как root , и нам нужно устанавливать его в root каждый раз, когда вводится предложение, то есть когда вводится символ «#».
Также требуется строковый тип stn для представления текущего искомого предложения.
Каждый раз, когда вы вводите символ, сначала проверьте, является ли он конечным знаком «#», если да, добавьте текущее предложение в дерево дерева, сбросьте соответствующие переменные и верните пустой массив.
-
Если нет, проверьте, содержит ли дочерний элемент, соответствующий текущему TrieNode, соответствующий узел c. Если нет, установите для curNode значение NULL и верните пустой массив.
-
Если он существует, обновите curNode до узла, соответствующего c, и выполните dfs на curNode.
DFS Когда мы впервые проверяем, что текущее предложение не является полным предложением.
После dfs нужно вынуть только первые три.Следует отметить, что может быть меньше 3 результатов, которые можно выбрать, поэтому следует добавить больше условных операторов для проверки того, что q пусто.
Наконец, извлеките все элементы из q.
анимация
Анимация сделана с AE, объем относительно большой, их 32 М, и ее нельзя воспроизвести в формате GIF, поэтому она принимает форму воспроизведения видео, и сторона с мобильным телефоном должна быть осторожна :)
благодарныйJun ChenБольшой парень обеспечивает техническую поддержку анимации и пополнения.
Код ссылки
C++
class TrieNode{
public:
string str;
int cnt;
unordered_map<char, TrieNode*> child;
TrieNode(): str(""), cnt(0){};
};
struct cmp{
bool operator() (const pair<string, int> &p1, const pair<string, int> &p2){
return p1.second < p2.second || (p1.second == p2.second && p1.first > p2.first);
}
};
class AutocompleteSystem {
public:
AutocompleteSystem(vector<string> sentences, vector<int> times) {
root = new TrieNode();
for(int i = 0; i < sentences.size(); i++){
insert(sentences[i], times[i]);
}
curNode = root;
stn = "";
}
vector<string> input(char c) {
if(c == '#'){
insert(stn, 1);
stn.clear();
curNode = root;
return {};
}
stn.push_back(c);
if(curNode && curNode->child.count(c)){
curNode = curNode->child[c];
}else{
curNode = NULL;
return {};
}
dfs(curNode);
vector<string> ret;
int n = 3;
while(n > 0 && !q.empty()){
ret.push_back(q.top().first);
q.pop();
n--;
}
while(!q.empty()) q.pop();
return ret;
}
void dfs(TrieNode* n){
if(n->str != ""){
q.push({n->str, n->cnt});
}
for(auto p : n->child){
dfs(p.second);
}
}
void insert(string s, int cnt){
TrieNode* cur = root;
for(auto c : s){
if(cur->child.count(c) == 0){
cur->child[c] = new TrieNode();
}
cur = cur->child[c];
}
cur->str = s;
cur->cnt += cnt;
}
private:
TrieNode *root, *curNode;
string stn;
priority_queue<pair<string,int>, vector<pair<string, int>>, cmp > q;
};
Python
Код предоставили друзья Тоби Цинь и Сяодун :)
class TrieNode:
def __init__(self):
self.children = dict()
self.sentences = set()
class AutocompleteSystem(object):
def __init__(self, sentences, times):
"""
:type sentences: List[str]
:type times: List[int]
"""
self.buffer = ''
self.stimes = collections.defaultdict(int)
self.trie = TrieNode()
for s, t in zip(sentences, times):
self.stimes[s] = t
self.addSentence(s)
self.tnode = self.trie
def input(self, c):
"""
:type c: str
:rtype: List[str]
"""
ans = []
if c != '#':
self.buffer += c
if self.tnode: self.tnode = self.tnode.children.get(c)
if self.tnode: ans = sorted(self.tnode.sentences, key=lambda x: (-self.stimes[x], x))[:3]
else:
self.stimes[self.buffer] += 1
self.addSentence(self.buffer)
self.buffer = ''
self.tnode = self.trie
return ans
def addSentence(self, sentence):
node = self.trie
for letter in sentence:
child = node.children.get(letter)
if child is None:
child = TrieNode()
node.children[letter] = child
node = child
child.sentences.add(sentence)