Лексикографически наименьшая строка с заданной строкой в качестве префикса

Дан массив arr[] , состоящий из N строк, и строка S размера M , задача состоит в том, чтобы найти лексикографически наименьшую строку, состоящую из строки S в качестве префикса. Если не существует ни одной строки, начинающейся с префикса S , выведите «-1» .

Примеры:

Input: arr[] = {“apple”, “appe”, “apl”, “aapl”, “appax”}, S = “app”
Output: appax
Explanation:
The lexicographical order of the strings consisting of “app” as the substring is {“aapl”, “apl”, “appax”, “appe”, “apple”}. The smallest lexicographic string containing is “appax”.

Input: arr[] = {“can”, “man”, “va”}, S = “van”
Output: -1

Подход: Данную проблему можно решить, отсортировав заданный массив строк arr[] так, чтобы все строки, начинающиеся с префикса S , встречались последовательно. Теперь пройдите по заданному массиву строк arr[] и, когда первая строка, чей префикс совпадает с S , напечатайте эту строку и прервите цикл. В противном случае выведите «-1» .

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

Временная сложность: O(M*K*N*log N), где K — максимальная длина строки в массиве arr[] .
Вспомогательное пространство: O(N)

Другой подход. Описанный выше подход также можно оптимизировать, используя структуру данных Trie, вставив все заданные строки в Trie, а затем проверив первую строку, существующую в Trie, с префиксом S .

Временная сложность: O(M*N)
Вспомогательное пространство: O(N)