Сложность: 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 {
func repeatedStringMatch(_ A: String, _ B: String) -> Int {
var q = 1
var S = A
while S.count < B.count {
S += A
q += 1
}
if S.contains(B) {
return q
}
if (S + A).contains(B) {
return q + 1
}
return -1
}
}Ставь 👍 и забирай 📚 Базу знаний