Найдите окончательную строку, увеличив префиксы заданной длины
Имея строку S и массив roll[] , где roll[i] представляет увеличение первых символов roll[i] в строке, задача состоит в том, чтобы увеличить все префиксы, упомянутые в массиве, и найти окончательную строку.
Примечание. Увеличение означает увеличение значения ASCII символа, например, увеличение «z» приведет к «a», увеличение «b» приведет к «c» и т. д.
Примеры :
Input: S = “bca”, roll[] = {1, 2, 3}
Output: eeb
Explanation: arr[0] = 1 means roll first character of string -> cca
arr[1] = 2 means roll first two characters of string -> dda
arr[2] = 3 means roll first three characters of string -> eeb
So final ans is “eeb”.Input: S = “zcza”, roll[] = {1, 1, 3, 4}
Output: debb
Подход : выполните шаги, чтобы решить эту проблему:
- Инициализируйте массив arr[] размера N + 1 и установите его равным 0.
- Перейдите массив a[] и увеличьте arr[0] на 1 и уменьшите arr[roll[i]] на 1. {поскольку мы используем индексацию, основанную на 0, поэтому мы делаем arr[roll[i]] -= 1 и не приб[ролл[i] + 1] -= 1}
- Запустите цикл от 1 до N и создайте массив префиксов, выполнив следующие действия: arr[i] += arr[i – 1] .
- Пройдите по массиву arr[] и вычислите arr[i] в диапазоне от 0 до 25, взяв его мод на 26 и проверьте:
- Если arr[i] + S[i] > 'z', то измените S[i] = (S[i] + arr[i] – 26) .
- В противном случае измените S[i] = S[i]+arr[i]
- После обхода массива arr[] верните S .
Ниже приведена реализация описанного выше подхода.
Временная сложность: O(N)
Вспомогательное пространство: O(N)
Статьи по Теме:
- Введение в строки — учебные пособия по структуре данных и алгоритмам
- Массив сумм префиксов — реализация и приложения в соревновательном программировании