Минимальные обороты, необходимые для удаления обеих строк

Даны две строки A и B , которые являются перестановками друг друга. Задача состоит в том, чтобы найти минимальное количество оборотов, необходимое для полного удаления обеих строк. Мы можем удалить первые символы обеих строк, если они совпадают. В противном случае строка поворачивается на одну позицию влево.

Примеры:

Input: A = “abcd”,  B = “bcda”
Output: 1
Explanation: rotate A, only one left rotation is required to make both strings equal

Input: 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.

1. Инициализировать вращения = 0 (Количество вращений)
2. Проверьте, совпадают ли первые символы обеих строк.
   • Если нет, то примените левое вращение к строке A и увеличьте вращение.
   • Если первые символы совпадают, удалите первый символ из обеих строк.
3. Проверьте, пусты ли обе строки.
   • Если да, то разорвите петлю.
   • В противном случае перейдите к шагу 2 и повторите его со следующего индекса.

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

Временная сложность: O(N ² )
Вспомогательное пространство: 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 ² )
Вспомогательное пространство : O(N)

Статьи по Теме:

• Введение в очередь — учебные пособия по структурам данных и алгоритмам
• Введение в строки — учебные пособия по структурам данных и алгоритмам