Дано: строка s, проверьте, можно ли ее воспроизвести, взяв подстроку, умноженную N раз.
Пример:
Строка: s = "abab"
Ответ: true
Пояснения: Это дважды подстрока "ab".
Пример 2:
Строка: s = "aba"
Ответ: false
Ограничения:
1 <= s.length <= 10^4
s состоит из строчных английских букв.
Решения:
1) Сравнения в цикле
Одинаковые решение, от менее оптимального, к более оптимальному:
ver1.
class Solution:
def repeatedSubstring(self, s: str) -> bool:
repeat = ''
for i in range(len(s) // 2):
repeat += s[i]
if len(s) % len(repeat) == 0:
if repeat * (len(s) // len(repeat)) == s:
return True
return False
ver 2 upd:
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
for i in range(1, len(s) // 2 + 1):
if len(s) % i == 0 and s[:i] * (len(s) // i) == s:
return True
return False
Мы перебираем все возможные длины подстрок (от 1 до половины длины входной строки).
Для каждой длины мы проверяем, можно ли сформировать строку, повторив текущую подстроку. Если да, то мы возвращаем True.
Если повторяющаяся подстрока не найдена, то после цикла мы возвращаем False.
Временная сложность: цикл даёт O(n) и slice даёт O(n) = O(n^2)
2) На подумать
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
s_fold = "".join((s[1:], s[:-1]))
return s in s_fold
или
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
return s in s[1:] + s[:-1]
copypaste @brianchiang_tw
Объяснение:
Алгоритм действий:
1) Создать новую переменную s_fold = s[ 1 : ] + s[ : -1 ]
2) Проверьте, можем ли мы найти s в s_fold или нет.
Если s имеет повторяющийся шаблон подстроки, то мы можем найти s в s_fold, согласно математическому обоснованию выше.
В противном случае s не может быть найдено.
Пример:
s = 'abab'
s_fold = 'bababa'
мы можем найти s в s_fold, где s_fold = 'bababa'
#2.
s = 'abac'
s_fold = 'bacaba'
мы не можем найти s в s_fold, где s_fold = 'bacaba', поэтому false
Временная сложность: операция in это O(n)
Пространственная сложность: 2 cлайса 2O(n)