Сортировка массива строк в заданном порядке | Сет-2

Опубликовано: 21 Сентября, 2022

Учитывая массив строк words[] и последовательный порядок алфавитов, задача состоит в том, чтобы отсортировать массив в соответствии с заданным порядком. Предположим, что словарь и слова содержат только строчные буквы английского алфавита.

Примеры:

Input: words[] = {“hello”, “geeksforgeeks”}, order[] = “hlabcdefgijkmnopqrstuvwxyz”
Output: hello geeksforgeeks 
Explanation: According to the given order ‘h’ occurs before ‘g’ and hence the words are considered to be sorted.

Input: words = {“word”, “world”, “row”}, order = “worldabcefghijkmnpqstuvxyz” 
Output: world word row 
Explanation: According to the given order ‘l’ occurs before ‘d’ hence the words “world” will be kept first.  

Подход: Данная проблема уже обсуждалась в статье здесь. В этой статье предлагается другой подход, использующий хеширование. Поскольку задан порядок алфавитов, его можно использовать в качестве ключа, где порядок[i] -й алфавит можно заменить на i -й алфавит. Например, в заданном порядке[] = «hlabcdefgijkmnopqrstuvwxyz» символ «h» можно заменить на «a» , символ «l» можно заменить на «b» и т. д . Используя это наблюдение, данную проблему можно решить, выполнив следующие шаги:

  • Создайте хеш -функцию, которая принимает ключ в качестве аргумента и заменяет все символы строки в соответствии с заданным ключом, т. е. символ x будет заменен символом, хранящимся в key[x] .
  • Используйте неупорядоченную карту encode , которая хранит последовательность символов в соответствии с заданным порядком, например, encode['h'] = 'a' , encode['l'] = 'b'… и так далее. Точно так же сохраните обратное в декодировании , т. Е. decode['a'] = 'h' , decode['b'] = 'l' … и так далее, которые можно использовать для восстановления исходного массива.
  • Отсортируйте массив после его хеширования, используя encode в качестве ключа.
  • Восстановите строки в отсортированном массиве, используя decode в качестве ключа.

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


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

РЕКОМЕНДУЕМЫЕ СТАТЬИ