Минимальные обороты, необходимые для удаления обеих строк
Даны две строки A и B , которые являются перестановками друг друга. Задача состоит в том, чтобы найти минимальное количество оборотов, необходимое для полного удаления обеих строк. Мы можем удалить первые символы обеих строк, если они совпадают. В противном случае строка поворачивается на одну позицию влево.
Примеры:
Input: A = “abcd”, B = “bcda”
Output: 1
Explanation: rotate A, only one left rotation is required to make both strings equalInput: A=”geek” B=”geek”
Output : 0
Explanation: Both strings are equal hence the number of operations is 0.
Подход:
The basic idea is to check if A is and B are rotations of each other or not.
- Инициализировать вращения = 0 (Количество вращений)
- Проверьте, совпадают ли первые символы обеих строк.
- Если нет, то примените левое вращение к строке A и увеличьте вращение.
- Если первые символы совпадают, удалите первый символ из обеих строк.
- Проверьте, пусты ли обе строки.
- Если да, то разорвите петлю.
- В противном случае перейдите к шагу 2 и повторите его со следующего индекса.
Ниже приведена реализация вышеуказанного подхода.
Временная сложность: O(N 2 )
Вспомогательное пространство: O(1)
Подход с использованием очереди:
We can solve this problem using queue for clockwise rotation. We will append characters of string A in queue and iterate over string B. And apply left rotation on queue if required. Else remove the first character from B and pop the queue front from the queue.
- Инициализировать переменную (например, rotates ) для хранения необходимого количества оборотов.
- Создайте очередь символов для хранения символов.
- Добавить все символы строки A в очередь.
- Начните итерацию по строке B и проверьте, совпадает ли первый символ обеих строк или нет.
- Если они совпадают, удалите строку.
- В противном случае требуется ротация.
- Рассчитать обороты:
- Создайте переменную (скажем, times ) для подсчета количества оборотов по часовой стрелке.
- Запустите цикл while и проверьте, не равны ли первые элементы. Если это так, увеличьте переменную времени и поместите самое переднее значение в очередь и вытолкните () очередь.
- Вернуть переменную времени.
- В качестве результата верните переменную вращений .
Ниже приведена реализация вышеуказанного подхода.
Временная сложность : O(N 2 )
Вспомогательное пространство : O(N)
Статьи по Теме:
- Введение в очередь — учебные пособия по структурам данных и алгоритмам
- Введение в строки — учебные пособия по структурам данных и алгоритмам