Проверьте, может ли строка быть сгенерирована путем объединения символов или самой строки.

Опубликовано: 19 Сентября, 2022

Учитывая целевую строку S , состоящую из строчных букв, задача состоит в том, чтобы создать эту строку, выполнив некоторую операцию над пустой строкой так, чтобы:

  • Первая операция заключается в добавлении строчной буквы к строке S и
  • Вторая операция заключается в добавлении копии S к самому себе.

Примечание . Первую операцию нельзя использовать непрерывно два раза.

Примеры:

Input: S = “xxyxxy”
Output: Yes

Explanation: First append ‘x’ to the empty string S. Now S = ”x”.
Use second operation. The string will be S = “xx”.
Append ‘y’ with the string. Then current string is “xxy”.
At last perform operation 2 to get the given string which is “xxyxxy”. 
Hence it is possible to make the given string S after performing operations.

Input: S = ”bee”

Output: No

Подход: Задача может быть решена на основе следующего наблюдения:

Наблюдения:

  • The first type of operation can be applied when the string is empty or immediately after an operation of the second type has been performed on the string. 
  • After every operation of the second type, the length of the resulting string is even. Therefore the operation of the first type can only be applied when the length of the string is even and finally results in an odd length string.
  • This means if the length of the string is even then the last operation performed on it has to be of the second type otherwise if the length of the string is odd the last operation performed on it has to be of the first type.

Выполните шаги, указанные ниже, чтобы реализовать вышеуказанную идею:

  • Начните с заданной строки и продолжайте двигаться, пока строка не станет пустой:
  • Если размер текущей строки нечетный,
    • Удалить последний символ строки (операция первого типа).
  • Если размер текущей строки четный,
    • Проверить, является ли эта строка копией двух одинаковых строк (операция второго типа), и уменьшить размер строки вдвое.
    • Если существующая строка не может быть получена одной операцией второго типа, остановите итерацию.
  • Если строка пуста в конце, то ее можно построить с помощью этих операций, в противном случае ее нельзя построить с помощью этих операций.

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

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

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