Сложность: medium
Даны две строки a и b. Верните минимальное количество повторений строки a, чтобы строка b стала её подстрокой. Если сделать b подстрокой a невозможно, верните -1.
Обратите внимание: строка "abc", повторенная 0 раз, это "", повторенная 1 раз - "abc", повторенная 2 раза - "abcabc".
Пример:
Input: a = "abcd", b = "cdabcdab"
Output: 3
Explanation: We return 3 because by repeating a three times "abcdabcdabcd", b is a substring of it.
👨💻 Алгоритм:
1⃣Найти минимальное количество повторений строки A, чтобы её длина стала больше или равна длине B. Это значение q = ceil(len(B) / len(A)).
2⃣Проверить, является ли B подстрокой строки A, повторенной q раз. Если да, вернуть q. Иначе, проверить строку A, повторенную (q+1) раз. Если B является подстрокой этой строки, вернуть q+1.
3⃣Если B не является подстрокой ни в одном из случаев, вернуть -1.
😎 Решение:
class Solution:
def repeatedStringMatch(self, A: str, B: str) -> int:
q = 1
S = A
while len(S) < len(B):
S += A
q += 1
if B in S:
return q
if B in S + A:
return q + 1
return -1
Ставь 👍 и забирай 📚 Базу знаний