Find Массив, образованный изменением префикса каждый раз, когда найден данный символ.

Опубликовано: 26 Февраля, 2023

Дан массив arr[] длины N , состоящий только из заглавных букв латинского алфавита и буквы ch . задача состоит в том, чтобы найти окончательный массив, который будет формироваться путем перестановки префикса каждый раз, когда в массиве встречается буква ch .

Примеры :

Input: arr[] = {‘A’, ‘B’, ‘X’, ‘C’, ‘D’, ‘X’, ‘F’}, ch= ‘X’
Output: D C X A B X F 
Explanation: 
First encounter of ‘X’ at index 2, Initial subarray = A, B, Final subarray = B, A, X.
Second encounter of ‘X’ at index 5, Initial subarray = B, A, X, C, D 
Final subarray = D, C, X, A, B, X(added).
Final subarray after traversing, = D, C, X, A, B, X, F

Input: arr[] = {‘A’, ‘B’, ‘C’, ‘D’, ‘E’}, ch = ‘F’
Output: A B C D E

Подход : Идея решения проблемы заключается в следующем:

If each portion between two occurrences of ch (or the ends of the array) is considered a segment, then the prefix reversals of the string can be visualised as appending the characters of a segment alternatively at the starting and the ending of string and keep expanding outwards. 

  • So idea is to push the element of the array into back of a list till ch occurs for first time. 
  • When first ch occurs, push the elements, including ch, to the front of the list till the next ch occurs. Again if ch occurs push the elements to the back of the list, including ch. 
  • So, the conclusion is that each time ch occurs, you have to change the direction of pushing the elements.

Note:  If there is odd number of K in the array, you need to reverse the list as we start pushing element from back.

Следуйте инструкциям ниже

  • Создайте список с именем li для хранения элементов
  • Создайте переменную с именем found , чтобы проверить, с какой стороны вы должны добавить элементы.
  • Если встречается ch, измените значение найденного с 1 на 0 или с 0 на 1.
    • Если найдено равно 1, добавьте элементы на передний план .
    • В противном случае добавьте элементы на задний план
  • Если ch встречается нечетное количество раз, переверните список и напечатайте, иначе напечатайте просто

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

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

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