Решения LeetCode (161 часть серии)
Это является частью серии объяснений решения LeetCode ( index ). Если вам понравилось это решение или нашел его полезным, Пожалуйста, как Этот пост и/или УПОТАТЬ Мое решение пост на форумах LeetCode Отказ
Проблема лецкода # 1268 (средний): Система поиска предложений
Описание:
( Перейти к : Идея решения Код : JavaScript | Python |. Java |. C ++
Учитывая массив строк Продукты
и струна Searchword.
. Мы хотим разработать систему, которая предлагает не более трех названий продуктов от Продукты
После каждого персонажа searchword
печатается. Предлагаемые продукты должны иметь общий префикс с Searchword.
. Если есть более трех товаров с общим префиксом, возвращают три лексикографически минимума.
Вернуть Список списков Из предложенного Продукты
После каждого персонажа searchword
печатается.
Примеры:
Вход: | продукты = [«Мобильный», «Мышь», «Монепот», «Монитор», «Коврик для мыши»], |
Вывод: | [[«Мобильный», «Монепот», «Монитор»], [«Мобильный», «Монепот», «Монитор»], [«Мышь», «Mousepad»], [«Мышь», «Mousepad»], [ «Мышь», «коврик для мыши»]] |
Объяснение: | продукты отсортированы лексикографически = [«Мобильный», «Монепот», «Монитор», «Мышь», «Mousepad»] После ввода M и MO всех товаров совпадают, и мы показываем пользователь [«Мобильный», «MoneyPot», «Монитор»] После набора MOU, Mous и Mouse System предлагает [«Мышь», «Mousepad»] |
Вход: | продукты = [“Гавана”], |
Вывод: | [«Гавана»], [«Гавана»], [«Гавана»], [«Гавана»], [«Гавана»], [«Гавана»]]] |
Вход: | Продукты = [«Сумки», «Багаж», «Баннер», «Коробка», «Скатки»], |
Вывод: | [«Багаж», «Сумки», «Баннер»], [«Багаж», «Сумки», «Баннер»], [«Багаж», «Сумки»], [«Сумки»]] |
Вход: | продукты = [“Гавана”], |
Вывод: | [[],[],[],[],[],[],[]] |
Ограничения:
1 длиной
- Нет повторных элементов в
продукты
. 1 товаров [I]. Длина * 10 ^ 4
- Все персонажи
Продукты [I]
строчные буквы английского языка. 1 длиной
- Все персонажи
searchword
строчные буквы английского языка.
Идея:
( Перейти к : Описание проблемы Код : JavaScript | Python |. Java |. C ++
Несмотря на то, что подсказки предлагают Бинарный поиск и а Три Оптимальное решение этой проблемы не нуждается в одном. Подстроки, сформированные путем добавления одной буквы одновременно из поискового слова ( S ), естественно, уже уже в лексикографическом порядке, как и результаты, которые нам проинструктированы в наш массив ответов ( ANS ) Отказ
Поэтому, если мы сортируем массив продуктов ( P ), нам следует только понадобиться только через P один раз в течение всего оставшегося процесса решения с помощью Сложность времени O (n) Отказ Один двоичный поиск потребуется только Журнал (N) Время , но мы должны были выполнить M.Length двоичные поиски, так что в целом они взяли бы O (m * log (n)) время по сравнению с O (n) Время простой итерации.
С ограничениями 1000 на обоих М и N. Двоичный поисковый маршрут будет максимальным в худшем сложности времени, чем итерацией. Независимо от того, сам сорт, который требуется для обоих, требует O (n * log (n)) Время уже, поэтому ни один из вариантов не может уменьшить общую сложность времени.
Поэтому для того, чтобы требовать только одного прохода через P , мы должны отслеживать текущие границы для диапазона матчей ( влево, справа ), то мы переживаем через персонажей ( c ) S . На каждой итерации мы сначала хотим переместить левый вперед и правильно Назад, чтобы сузить диапазон матчей на основе нового значения слияние .
Тогда мы можем добавить следующие три элемента P к нашему массиву результатов ( res ), до тех пор, пока они падают внутри диапазона [левый, справа] Отказ Как только это сделано, мы можем добавить res. к анс и перейти к следующей итерации.
Как только мы закончили итерацию через S мы можем Вернуть АНС Отказ
- Сложность времени: o (n * log (n)) где N это длина P
- Космическая сложность: O (1) исключая выходное пространство, необходимое для анс
Код JavaScript:
( Перейти к : Описание проблемы Идея решения
var suggestedProducts = function(P, S) { P.sort() let ans = [], left = 0, right = P.length - 1 for (let i = 0; i < S.length; i++) { let c = S.charAt(i), res = [] while (P[left]?.charAt(i) < c) left++ while (P[right]?.charAt(i) > c) right-- for (let j = 0; j < 3 && left + j <= right; j++) res.push(P[left+j]) ans.push(res) } return ans };
Код Python:
( Перейти к : Описание проблемы Идея решения
class Solution: def suggestedProducts(self, P: List[str], S: str) -> List[List[str]]: P.sort() ans, left, right = [], 0, len(P) - 1 for i in range(len(S)): c, res = S[i], [] while left <= right and (len(P[left]) == i or P[left][i] < c): left += 1 while left <= right and (len(P[right]) == i or P[right][i] > c): right -= 1 for j in range(3): if left + j > right: break else: res.append(P[left+j]) ans.append(res) return ans
Java код:
( Перейти к : Описание проблемы Идея решения
class Solution { public List> suggestedProducts(String[] P, String S) { Arrays.sort(P); List
> ans = new ArrayList<>(); int left = 0, right = P.length - 1; for (int i = 0; i < S.length(); i++) { List
res = new ArrayList<>(); char c = S.charAt(i); while (left <= right && (P[left].length() == i || P[left].charAt(i) < c)) left++; while (left <= right && (P[right].length() == i || P[right].charAt(i) > c)) right--; for (int j = 0; j < 3 && left + j <= right; j++) res.add(P[left+j]); ans.add(res); } return ans; } }
C ++ код:
( Перейти к : Описание проблемы Идея решения
class Solution { public: vector> suggestedProducts(vector & P, string S) { sort(P.begin(), P.end()); vector > ans; int left = 0, right = P.size() - 1; for (int i = 0; i < S.length(); i++) { vector res; char c = S[i]; while (left <= right && (P[left].length() == i || P[left][i] < c)) left++; while (left <= right && (P[right].length() == i || P[right][i] > c)) right--; for (int j = 0; j < 3 && left + j <= right; j++) res.push_back(P[left+j]); ans.push_back(res); } return ans; } };
Решения LeetCode (161 часть серии)
Оригинал: “https://dev.to/seanpgallivan/solution-search-suggestions-system-90e”