Дизайн рекомендательной системы по поисковому слову

 Источник: https://leetcode.com/problems/search-suggestions-system 

Дан строковый массив products и сттрока searchWord.

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

Пример 1:

Дано: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
Результат: [["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]
Пояснение: продукты отсортированные в лексикографическом порядке = ["mobile","moneypot","monitor","mouse","mousepad"].
После введения m и mo мы показываем пользователю ["mobile","moneypot","monitor"].
После введения mou, mous и mouse система рекомендует ["mouse","mousepad"].

Пример 2:

Дано: products = ["havana"], searchWord = "havana"
Результат: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]
Пояснение: Единственное слово "havana" бедет постоянно предлагаться в процессе введения поискового слова.

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

• 1 <= products.length <= 1000
• 1 <= products[i].length <= 3000
• 1 <= sum(products[i].length) <= 2 * 104
• Все строки в products уникальны.
• products[i] состоят из строчных букв английского алфафита.
• 1 <= searchWord.length <= 1000
• searchWord состоит из строчных букв английского алфафита.

Идея решения

Когда возникает вопрос о множественных строках и префиксах, то лучше всего для его решения подходит такая структура данных, как Trie (префиксное дерево). В нашей задаче также содержится требование вернуть результат в лексикографическом порядке. В префиксном дереве слова также хранятся в лексикографическом порядке. Наша задача сократить обход до 3 элементов.

Алгоритм:

1. Создать префиксное дерево из слов массива products. 
2. Сканировать поисковое слово searchWord,составляя из него поисковый префикс. 
3. После очередного добавления буквы к поисковому префиксу, обойти префиксное дерево и идентифицировать этот префикс. 
4. От вершины префикса в дереве начать поиск в глубину для идентификации полных слов с этим префиксом. 
5. Выдать результат, как только 3 слова будут найдены.
   

Имплементация 

// Класс Trie с функцией поиска 3 слов с заданным префиксом
class Trie {

    // Определяем вершину дерева
    class Node {
        boolean isWord = false;
        List<Node> children = Arrays.asList(new Node[26]);
    };
    Node Root, curr;
    List<String> resultBuffer;

    // DFS с заданным префиксом, размер ответа лимитирован 3 элементами
    void dfsWithPrefix(Node curr, String word) {
// проверка условий завершения поиска:
// найдено три слова
        if (resultBuffer.size() == 3)
            return;
// если в текущей точке у нас слово (а не его префикс), то добавляем его в буфер результата
        if (curr.isWord)
            resultBuffer.add(word);

        // Идем в глубину по вершинам-детям текущей вершины, если они существуют
        for (char c = 'a'; c <= 'z'; c++)
            if (curr.children.get(c - 'a') != null)
                dfsWithPrefix(curr.children.get(c - 'a'), word + c);
    }

// СОЗДАНИЕ ДЕРЕВА ПРЕФИКСОВ
    Trie() {
        Root = new Node();
    }

    // Добавляем строку в префиксное дерево
    void insert(String s) {

        // Устанавливаем указатель на корень
        curr = Root;
        for (char c : s.toCharArray()) {  // итерация по всем буквам слова
 // если в дереве ещё нет вершины, соответствующей букве в текущем префиксе, то создаем ее
            if (curr.children.get(c - 'a') == null)
                curr.children.set(c - 'a', new Node());
// перемещаем указатель на текущую букву слова
            curr = curr.children.get(c - 'a');
        }

        // Как только доходим до конца вставляемого слова,
        // то помечаем вершину, что это полное слово
        curr.isWord = true;
    }

// обход дерева с заданным префиксом
    List<String> getWordsStartingWith(String prefix) {
// устанавливем указатель на корень
        curr = Root;
        resultBuffer = new ArrayList<String>();
        // Сканируем префикс
        for (char c : prefix.toCharArray()) {
// если в дереве нет соответствия текущему префиксу,
// то возвращаем то, что есть в буфере результата
            if (curr.children.get(c - 'a') == null)
                return resultBuffer;
// а иначе перемещаем указатель на текущую букву префикса
            curr = curr.children.get(c - 'a');
        }
// делаем поиск вглубину для обнаружения слов с этим префиксом,
// внутри метода заполняется буфер результата
        dfsWithPrefix(curr, prefix);
        return resultBuffer;  // возвращаем буфер результата
    }
};


class Solution {
    List<List<String>> suggestedProducts(String[] products,
                                         String searchWord) {
        Trie trie = new Trie();
        List<List<String>> result = new ArrayList<>();
        // Создаем дерево префиксов для списка продуктов
        for (String w : products)
            trie.insert(w);

        String prefix = new String();
// сканируем поисковое слово
        for (char c : searchWord.toCharArray()) {
            prefix += c; // и для каждой очередной буквы создаем префикс

// для текущего префикса сканируем дерево префиксов
            result.add(trie.getWordsStartingWith(prefix));
        }
        return result;
    }
};

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

• Сложность по времени : $O(M)$ чтобы построить префиксное дерево trie, где M - это суммарное число букв в массиве products. Для каждого prefix мы находим вершину в дереве, которой он соответствует, за $O(\text{len(prefix)})$ , и dfs для поиска не более 3 полных слов - это 3*длинну самомго длинного слова, что можно считать константой O(1). Поэтому общая сложнось по времени детерминирована временем, которое необходимо, чтоб построить trie.

• Сложность по памяти : $O(26n)=O(n)$. Здесь n- это число вершин вtrie. 26 - это размер алфавита.