Количество строк массива с заданными префиксами для Q-запроса

Имея два массива строк, содержащих слова[] и запросы[] , имеющие N и Q строк соответственно, задача состоит в том, чтобы найти количество строк из слов[] , имеющих запросы[i], в качестве префикса для всех строк в запросах[] .

Примеры:

Input: words[] = { “geeks”, “geeks”, “geeks for geeks”, “string”, “strong” }, queries[] = { “geek”, “gel”, “str” }
Output: 3, 0, 2
Explanation:
1st query “geek” is present in 3 words in the list as a prefix, { “geekf”, “geeks”, “geeksforgeeks” }
2nd query “gel” is not present in any word in the list as a prefix 
3rd query “str” is present in 2 words in the list as a prefix, {“string”, “strong”}   

Input: words[] = { “apple”, “app”, “ape”, “allien”, “a”, “box”, “boxing” }, queries[] = { “a”, “ap”, “b”, “app”, “book” }
Output: 5, 3, 2, 2, 0
Explanation:
1st query “a” is present in 5 words in the list as a prefix, { “apple”, “app”, “ape”, “allien”, “a” }
2nd query “ap” is present in 3 words in the list as a prefix, { “apple”, “app”, “ape” }
3rd query “b” is present in 2 words in the list as a prefix, {“box”, “boxing”} 
4th query “app” is present in 2 words in the list as a prefix, {“apple”, “app“}
5th query “book” is not present in any word in the list as a prefix

Наивный подход: проблема может быть решена на основе следующей идеи:

For each query traverse through every word in the list and check whether the word has a prefix as current query or not.

• Создайте фиктивный вектор ans для хранения результирующего массива.
• Начните обход запросов [] и инициализируйте переменную счетчика count , чтобы сохранить количество слов с префиксами в качестве текущего запроса.
  • Если размер любого слова на любой i- ^й итерации меньше размера запроса, итерация пропускается.
  • Если префикс найден в словах [] , увеличьте переменную счетчика.
  • Нажмите количество префиксов в векторе ans .
• Верните ответ .

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N * Q * M), где M = максимальная длина строки в запросах[]
Вспомогательное пространство: O(N)

Эффективный подход: проблема может быть решена эффективно на основе следующего подхода.

We have to use such a data structure to match the string to find out if it is prefix of another string in optimal time. Trie can help us in this problem.

Build a trie and insert the strings of word[] in the trie. where each node will also keep a count of strings with that prefix. Then while traversing through queries[] find the prefix and the count associated with it. The structure of a trie node will be like the following:

• children: This field is used for mapping from a character to the next level trie node
• isEndOfWord: This field is used to distinguish the node as end of word node
• num: This field is used to count the number of times a node is visited during insertion in trie

Следуйте шагам, указанным ниже, чтобы реализовать идею:

• Вставьте список строк в trie таким образом, чтобы каждая строка в списке была вставлена как отдельный узел trie .
• Во время вставки обновите все поля в каждом узле дерева.
• Для каждого запроса проходим по дереву , пока не достигнем последнего символа данного префикса query[i] .
• Значение поля num в последнем узле префикса — это количество строк word[] , имеющих данный префикс.
• Для каждого запроса сохраните это число в векторе ответов.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(Q * x + N*L), Где x — самое длинное слово в запросе, а L — длина самого длинного слова, вставленного в дерево.
Вспомогательное пространство: O(N * список [i])