Проблема 9:
Предположим, у вас есть метод isSubString, который проверяет, является ли одно слово подстрокой другого. При наличии двух строк s1 и s2 напишите код для проверки того, является ли s2 вращением s2, используя только один вызов isSubString (например, «waterbottle» — это вращение «erbottlewat»)

Input:
s1 = "waterbottle"
s2 = "erbottlewat"
Output:
True
s2 is a rotation of s1.

Подход 1:

  1. Продолжайте вращать входную строку s1 по одному символу за раз и сравнивать ее с повернутой строкой.
  2. Если строки равны, то s2 — это вращение s1.
  3. После достижения конечной точки s1, если строки не равны, тогда s2 не является вращением s1

Временная сложность: O(N²)
Пространственная сложность: O(1)

Подход 2:
Если мы пройдемся по постановке задачи, нам сказали использовать метод isSubString, чтобы определить, является ли строка s2 поворотом входной строки s1.

Итак, как мы можем использовать метод isSubString, чтобы проверить, является ли s2 поворотом строки s1?
Учитывая входную строку:
s1 = «waterbottle»
s2 = «erbottlewat»

Мы можем разбить повернутую строку s2 следующим образом:
s2 = s1.substr(3, 11) + s1.substr(0, 3)

Если мы соединим s1 дважды =› «watererbottlewaterbottle»

Затем мы видим, что строка «erbottlewat» является подстрокой объединенной строки s1.
Итак, окончательный подход сводится к следующему:

  1. Объединить строку s1 с самой собой
  2. Проверьте, является ли строка s2 подстрокой объединенной строки s1.
  3. Если подстрока является частью конкатенированной строки, то строки чередуются друг с другом.

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

Итак, это два подхода к решению задачи вращения струны.

Вот и все!! Мы решили вопрос!