Сложность: 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 {
function repeatedStringMatch($A, $B) {
$q = 1;
$S = $A;
while (strlen($S) < strlen($B)) {
$S .= $A;
$q++;
}
if (strpos($S, $B) !== false) return $q;
if (strpos($S . $A, $B) !== false) return $q + 1;
return -1;
}
}Ставь 👍 и забирай 📚 Базу знаний