Программа Javascript для поиска лексикографически наименьшей повернутой последовательности | Набор 2
Опубликовано: 2 Сентября, 2022
Напишите код для поиска лексикографического минимума в циклическом массиве, например, для массива BCABDADAB лексикографический минимум равен ABBCABDAD.
Входное ограничение: 1 < n < 1000
Примеры:
Input: GEEKSQUIZ Output: EEKSQUIZG Input: GFG Output: FGG Input : CAPABCQ Output : ABCQCAP
Мы обсудили решение O(n 2 Logn) в лексикографически минимальном вращении строки | Установите 1. Здесь нам нужно найти начальный индекс минимального вращения, а затем вывести вращение.
1) Initially assume 0 to be current min starting index. 2) Loop through i = 1 to n-1. a) For each i compare sequence starting at i with current min starting index b) If sequence starting at i is lexicographically smaller, update current min starting index.
Вот псевдокод для алгоритма
function findIndexForSmallestSequence(S, n): result = 0 for i = 1:n-1 if (sequence beginning at i < sequence beginning at result) result = i end if end for return result
Вот реализация вышеуказанного алгоритма.
Выход:
AADCACBC
Временная сложность: O(n^2)
Вспомогательное пространство: O(1)
Пожалуйста, обратитесь к полной статье о лексикографически наименьшей повернутой последовательности | Набор 2 для более подробной информации!