Система поиска подсказок

Средняя

medium , trie , binary search

03 December 2024

Описание задачи #

Дан массив строк products, представляющий доступные названия продуктов, и строка searchWord, представляющая искомое слово, вводимое пользователем.

Реализуйте функцию, которая возвращает массив массивов, где:

Каждый подмассив содержит список подсказок для соответствующего префикса строки searchWord. Первый подмассив соответствует префиксу из первого символа строки searchWord, второй — префиксу из первых двух символов, и так далее.
Каждый подмассив включает до трех продуктов из products, отсортированных в лексикографическом порядке.
Если для какого-либо префикса не найдено совпадений, соответствующий подмассив должен быть пустым.

Ограничения #

1 <= products.length <= 1000 — количество продуктов.
1 <= products[i].length <= 3000 — длина каждой строки продукта.
1 <= searchWord.length <= 1000 — длина строки поиска.
Все строки состоят только из строчных латинских букв.

Примеры #

Продукты: products = ["mobile","mouse","moneypot","monitor","mousepad"]

Искомое слово: searchWord = "mouse"

Ответ: [

["mobile","moneypot","monitor"], // список подсказок для префикса "m"

["mobile","moneypot","monitor"], // список подсказок для префикса "mo"

["mouse","mousepad"], // список подсказок для префикса "mou"

["mouse","mousepad"], // список подсказок для префикса "mous"

["mouse","mousepad"], // список подсказок для префикса "mouse"

]
Продукты: products = ["havana"]

Искомое слово: searchWord = "havana"

Ответ: [

["havana"], // список подсказок для префикса "h"

["havana"], // список подсказок для префикса "ha"

["havana"], // список подсказок для префикса "hav"

["havana"], // список подсказок для префикса "hava"

["havana"], // список подсказок для префикса "havan"

["havana"], // список подсказок для префикса "havana"

]

Решение через префиксное дерево #

Задачи, в которых необходимо находить строки по заданному префиксу, обычно идеально решаются с использованием структуры данных под названием "Префиксное дерево (Trie)".

Для этого нам необходимо имплементировать саму структуру данных и метод, который по заданному префиксу будет возвращать конечные слова, начинающиеся с этого префикса. Чтобы оптимизировать поиск и избежать выполнения сортировки в процессе работы, помимо хеш-таблицы с дочерними узлами можно хранить отсортированный список ключей. Этот список будет формироваться или обновляться во время добавления новых слов.

Таким образом, решение задачи включает два этапа:

Преобразование входящего массива products в префиксное дерево.
Последовательный обход строки searchWord по символам с извлечением подсказок для каждого префикса.

Реализация #

package search_suggestions_system

import (
	"sort"
)

func suggestedProductsTrie(products []string, searchWord string) [][]string {
	root := &trie{
		children: make(map[rune]*trie),
	}

	sort.Strings(products)
	for _, p := range products {
		root.Insert(p)
	}

	runeSearch := []rune(searchWord)
	worldStart, exist := root.children[runeSearch[0]]
	if !exist {
		return root.gd(runeSearch)
	}

	suggestions := worldStart.Closest(runeSearch[1:], 3)
	res := make([][]string, len(suggestions))
	prev := []string{}
	i := len(suggestions) - 1
	if i > 0 {
		prev = suggestions[i][:]
		res[i] = prev
		i--
	}

	for ; i >= 0; i-- {
		newItem := suggestions[i][:]
		if len(prev) == 0 {
			res[i] = newItem
			prev = newItem[:]
			continue
		} else if len(newItem) == 0 {
			res[i] = prev[:]
			continue
		}

		newItem = append(newItem, prev...)
		sort.Strings(newItem)
		if len(newItem) > 3 {
			newItem = newItem[:3]
		}

		res[i] = newItem
		prev = newItem[:]
	}

	return res
}

type trie struct {
	world    string
	sort     []rune
	children map[rune]*trie
}

func (t *trie) Insert(word string) {
	t.insert(word, []rune(word))
}

func (t *trie) insert(origin string, word []rune) {
	if len(word) == 0 {
		t.world = origin
		return
	}

	child, exist := t.children[word[0]]
	if !exist {
		child = &trie{
			children: make(map[rune]*trie),
			sort:     make([]rune, 0, 5),
		}

		t.children[word[0]] = child
		t.sort = append(t.sort, word[0])
	}

	child.insert(origin, word[1:])
}

func (t *trie) Closest(prefix []rune, count int) [][]string {
	res := make([][]string, 0, len(prefix))
	var excludeRune *rune
	if len(prefix) > 0 {
		excludeRune = &prefix[0]
	}

	res = append(res, t.exactWorlds(excludeRune, count))

	if len(prefix) == 0 {
		return res
	}

	child, exist := t.children[prefix[0]]
	if !exist {
		res = [][]string{t.exactWorlds(nil, count)}
		return append(res, t.gd(prefix)...)
	}

	return append(res, child.Closest(prefix[1:], count)...)
}

func (t *trie) exactWorlds(excludeRune *rune, n int) []string {
	res := make([]string, 0, n)
	if len(t.world) > 0 {
		res = append(res, t.world)
		n--
	}

	if n == 0 {
		return res
	}

	for _, childRune := range t.sort {
		if excludeRune != nil && childRune == *excludeRune {
			continue
		}
		childWorlds := t.children[childRune].exactWorlds(nil, n)
		if len(childWorlds) >= n {
			return append(res, childWorlds[:n]...)
		}

		res = append(res, childWorlds...)
		n = n - len(childWorlds)
		if n == 0 {
			break
		}
	}

	return res
}

func (t *trie) gd(prefix []rune) [][]string {
	res := make([][]string, 0, len(prefix))
	for range prefix {
		res = append(res, []string{})
	}

	return res
}

class Trie {
	word: string = '';
	sort: string[] = [];
	children: Map<string, Trie> = new Map();

	insert(word: string): void {
		this._insert(word, [...word]);
	}

	private _insert(origin: string, word: string[]): void {
		if (word.length === 0) {
			this.word = origin;
			return;
		}

		const char = word[0];
		let child = this.children.get(char);

		if (!child) {
			child = new Trie();
			this.children.set(char, child);
			this.sort.push(char);
		}

		child._insert(origin, word.slice(1));
	}

	closest(prefix: string[], count: number): string[][] {
		const res: string[][] = [];
		let excludeChar: string | null = null;

		if (prefix.length > 0) {
			excludeChar = prefix[0];
		}

		res.push(this.exactWords(excludeChar, count));

		if (prefix.length === 0) {
			return res;
		}

		const child = this.children.get(prefix[0]);
		if (!child) {
			res[0] = this.exactWords(null, count);
			return res.concat(this.gd(prefix));
		}

		return res.concat(child.closest(prefix.slice(1), count));
	}

	private exactWords(excludeChar: string | null, n: number): string[] {
		let res: string[] = [];
		if (this.word.length > 0) {
			res.push(this.word);
			n--;
		}

		if (n === 0) {
			return res;
		}

		for (const childChar of this.sort) {
			if (excludeChar !== null && childChar === excludeChar) {
				continue;
			}

			const childWords = this.children.get(childChar)!.exactWords(null, n);
			if (childWords.length >= n) {
				return res.concat(childWords.slice(0, n));
			}

			res = res.concat(childWords);
			n -= childWords.length;

			if (n === 0) {
				break;
			}
		}

		return res;
	}

	gd(prefix: string[]): string[][] {
		const res: string[][] = [];
		for (let i = 0; i < prefix.length; i++) {
			res.push([]);
		}
		return res;
	}
}

export function suggestedProductsTrie(products: string[], searchWord: string): string[][] {
	const root = new Trie();

	products.sort();

	for (const p of products) {
		root.insert(p);
	}

	const runeSearch = [...searchWord];
	const firstChar = runeSearch[0];
	const worldStart = root.children.get(firstChar);

	if (!worldStart) {
		return root.gd(runeSearch);
	}

	const suggestions = worldStart.closest(runeSearch.slice(1), 3);
	const res: string[][] = new Array(suggestions.length);
	let prev: string[] = [];
	let i = suggestions.length - 1;

	if (i >= 0) {
		prev = suggestions[i].slice();
		res[i] = prev;
		i--;
	}

	for (; i >= 0; i--) {
		let newItem = suggestions[i].slice();

		if (prev.length === 0) {
			res[i] = newItem;
			prev = newItem.slice();
			continue;
		} else if (newItem.length === 0) {
			res[i] = prev.slice();
			continue;
		}

		newItem = newItem.concat(prev);
		newItem.sort();

		if (newItem.length > 3) {
			newItem = newItem.slice(0, 3);
		}

		res[i] = newItem;
		prev = newItem.slice();
	}

	return res;
}

Оценка сложности #

По времени

Преобразование массива в префиксное дерево: #

Для добавления слова длиной m в дерево потребуется O(m) операций.
Таким образом, для массива из n слов общее время составит O(m * n), где m — длина самого длинного слова в products, а n — количество слов в массиве.

Поиск подсказок по префиксу: #

Поиск подсказок по префиксу можно оценить в O(m), где m — длина самого длинного слова в products
Так как searchWord имеет длину s, для каждого из ее s префиксов нужно выполнить поиск подсказок. В сумме поиск займет O(s * m).

Итоговая оценка сложности: #

Сложность всего алгоритма можно выразить как: O(m*n+s*m) где:

m — длина самого длинного слова в products,
n — количество слов в массиве products,
s — длина строки searchWord.

По памяти

Для решения задачи нам потребуется память под префиксное дерево. В худшем случае ее можно оценить в O(m*n), где m - длина самого длинного слова в products, а n - длина массива products.

Возможные оптимизации префиксного дерева #

Избегаем лишних поисков в глубину #

Первое, что бросается в глаза, — необходимость для каждого префикса спускаться вниз по дереву вплоть до листовых узлов. Это приводит к дублирующейся работе, так как для многих префиксов списки подсказок будут идентичны. Особенно это заметно на длинных префиксах, где вариативность подсказок значительно ниже, чем для более коротких префиксов.

Чтобы избежать этого, можно изменить подход: вместо того чтобы начинать поиск с самого короткого префикса и двигаться вниз, мы можем стартовать с максимального префикса и подниматься вверх по дереву. В этом случае слова будут "всплывать" из нижележащих узлов к вышележащим, а спускаться вниз потребуется только в тех случаях, когда вариативность дочерних узлов у вышележащей ноды увеличивается по сравнению с текущей.

Хотя такая оптимизация может улучшить производительность в реальных условиях, она не изменит асимптотическую сложность алгоритма.

Оптимизация за счет памяти #

В реальной жизни память обычно дешевле, чем процессорное время, а операции чтения выполняются гораздо чаще, чем операции записи. Более того, размер каталога продуктов, как правило, невелик. Учитывая эти вводные, можно существенно оптимизировать решение задачи, модифицировав префиксное дерево.

Мы можем хранить в каждой ноде дерева дополнительный массив suggestions, содержащий ссылки на итоговые продукты, которые будут возвращаться в качестве подсказок. Это позволит избежать поиска в глубину при извлечении подсказок, что сократит сложность с O(s * m) до O(s), где s — длина строки searchWord. В реальных условиях такая оптимизация может значительно улучшить производительность, используя дешевый ресурс памяти.

Однако такая модификация влияет на сложность вставки слова в дерево. Теперь вставка потребует времени O(m * n * m), так как для каждой затронутой ноды при добавлении нового слова нужно будет пересчитывать массив подсказок, спускаясь по дереву.

В рамках данной задачи, где различия между нагрузками на чтение и запись не учитываются, эта оптимизация скорее ухудшает производительность. Увеличение затрат на вставку может перевесить преимущества, особенно при большом количестве операций записи.

Решение через бинарный поиск #

Особенность данной задачи заключается в том, что преобразование исходного массива в другую структуру данных можно рассматривать как запись (пишущую нагрузку), а поиск — как чтение (читающую нагрузку). Таким образом, в рамках этой задачи запись значительно превышает чтение, что нетипично для классических поисковых систем.

Чтобы достичь оптимального результата, необходимо минимизировать модификацию исходного массива. Если отсортировать массив products, все подсказки для одного префикса будут находиться рядом друг с другом. Это позволяет упростить задачу поиска подсказок по префиксу следующим образом:

Найти в отсортированном массиве индекс первого слова, которое начинается с заданного префикса.
Проверить два следующих слова за найденным индексом, чтобы определить, соответствуют ли они нужному префиксу.

Для нахождения первого слова с нужным префиксом можно использовать модифицированный бинарный поиск, который эффективно отыскивает начальную позицию префикса в отсортированном массиве.

Этот подход позволяет минимизировать изменения исходного массива, сохраняя оптимальную производительность поиска благодаря использованию сортировки и бинарного поиска.

Данную реализацию можно дополнительно оптимизировать:

В отсортированном массиве подсказки для следующего префикса гарантированно будут находиться либо в том же диапазоне, что и для текущего префикса, либо правее. Это позволяет ограничить область бинарного поиска, начиная с предыдущего диапазона, вместо выполнения поиска по всему массиву.
Линейный проход назад в процессе бинарного поиска для определения первого индекса слова, начинающегося с заданного префикса, можно устранить. Для этого можно модифицировать бинарный поиск так, чтобы он сразу возвращал индекс первого подходящего элемента.

Реализация #

package search_suggestions_system

import (
	"sort"
	"strings"
)

func suggestedProducts(products []string, searchWord string) [][]string {
	sort.Strings(products)
	res := make([][]string, 0, len(searchWord))

	var idx int
	items := products
	for idx = range searchWord {
		items, _ = suggestions(items, searchWord[:idx+1])
		if len(items) == 0 {
			break
		}

		maxLen := 3
		if len(items) < maxLen {
			maxLen = len(items)
		}
		res = append(res, items[:maxLen])
	}

	if idx < len(searchWord)-1 {
		res = gd(res, len(searchWord)-idx)
	}

	return res
}

func suggestions(products []string, prefix string) ([]string, bool) {
	startIdx := findFirstProductWithPrefix(products, prefix)
	if startIdx == -1 {
		return []string{}, true
	}

	res := make([]string, 0, 3)

	for i := startIdx; i < len(products); i++ {
		if !strings.HasPrefix(products[i], prefix) {
			break
		}

		res = append(res, products[i])
	}

	return res, false
}

func findFirstProductWithPrefix(products []string, prefix string) int {
	strWithPrefixIdx := -1
	startIdx, endIdx := 0, len(products)-1

	for startIdx <= endIdx {
		middleIdx := (endIdx + startIdx) / 2

		if strings.HasPrefix(products[middleIdx], prefix) {
			strWithPrefixIdx = middleIdx
			break
		}
		productRunes := []rune(products[middleIdx])

		for idx, char := range prefix {
			if idx > len(productRunes)-1 {
				startIdx = middleIdx + 1
				break
			}

			if productRunes[idx] == char {
				continue
			}

			if productRunes[idx] < char {
				startIdx = middleIdx + 1
			} else {
				endIdx = middleIdx - 1
			}

			break
		}
	}

	res := -1
	for i := strWithPrefixIdx; i >= 0; i-- {
		if strings.HasPrefix(products[i], prefix) {
			res = i
			continue
		}

		break
	}

	return res
}

func gd(res [][]string, tailLength int) [][]string {
	for i := 0; i < tailLength; i++ {
		res = append(res, []string{})
	}

	return res
}

export const suggestedProducts = (products: string[], searchWord: string): string[][] => {
    products.sort();
    let res: string[][] = [];
    let items = products;

    for (let idx = 0; idx < searchWord.length; idx++) {
        const prefix = searchWord.substring(0, idx + 1);
        items = suggestions(items, prefix);

        if (items.length === 0) {
            break;
        }

        const maxLen = Math.min(3, items.length);
        res.push(items.slice(0, maxLen));
    }

    res = gd(res, searchWord.length - res.length);

    return res;
}

export const suggestions = (products: string[], prefix: string): string[] => {
    const startIdx = findFirstProductWithPrefix(products, prefix);

    if (startIdx === -1) {
        return [];
    }

    const res: string[] = [];

    for (let i = startIdx; i < products.length; i++) {
        if (!products[i].startsWith(prefix)) {
            break;
        }
        res.push(products[i]);
    }

    return res;
}

export const findFirstProductWithPrefix = (products: string[], prefix: string): number => {
    let left = 0;
    let right = products.length - 1;
    let res = -1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (products[mid].startsWith(prefix)) {
            res = mid;
            right = mid - 1; // Ищем самое раннее вхождение
        } else if (products[mid] < prefix) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return res;
}

export const gd = (res: string[][], tailLength: number): string[][] => {
    for (let i = 0; i < tailLength; i++) {
        res.push([]);
    }
    return res;
}

Оценка сложности #

По времени

Нам предварительно необходимо отсортировать исходный массив, а после совершить s бинарных поисков. Таким образом итоговую сложность можно оценить в O(s*log(n)), где n длина массива products, а s — длина searchWord.

По памяти

Память для данной реализации константна - O(1).

Оригинал задачи на Leetcode

Algorithmics

Система поиска подсказок

Описание задачи #

Ограничения #

Примеры #

Решение через префиксное дерево #

Реализация #

Оценка сложности #

Преобразование массива в префиксное дерево: #

Поиск подсказок по префиксу: #

Итоговая оценка сложности: #

Возможные оптимизации префиксного дерева #

Избегаем лишних поисков в глубину #

Оптимизация за счет памяти #

Решение через бинарный поиск #

Реализация #

Оценка сложности #