Welcome to Subscribe On Youtube
686. Repeated String Match
Description
Given two strings a and b, return the minimum number of times you should repeat string a so that string b is a substring of it. If it is impossible for b to be a substring of a after repeating it, return -1.
Notice: string "abc" repeated 0 times is "", repeated 1 time is "abc" and repeated 2 times is "abcabc".
Example 1:
Input: a = "abcd", b = "cdabcdab" Output: 3 Explanation: We return 3 because by repeating a three times "abcdabcdabcd", b is a substring of it.
Example 2:
Input: a = "a", b = "aa" Output: 2
Constraints:
1 <= a.length, b.length <= 104aandbconsist of lowercase English letters.
Solutions
-
class Solution { public int repeatedStringMatch(String a, String b) { int m = a.length(), n = b.length(); int ans = (n + m - 1) / m; StringBuilder t = new StringBuilder(a.repeat(ans)); for (int i = 0; i < 3; ++i) { if (t.toString().contains(b)) { return ans; } ++ans; t.append(a); } return -1; } } -
class Solution { public: int repeatedStringMatch(string a, string b) { int m = a.size(), n = b.size(); int ans = (n + m - 1) / m; string t = ""; for (int i = 0; i < ans; ++i) t += a; for (int i = 0; i < 3; ++i) { if (t.find(b) != -1) return ans; ++ans; t += a; } return -1; } }; -
class Solution: def repeatedStringMatch(self, a: str, b: str) -> int: m, n = len(a), len(b) ans = ceil(n / m) t = [a] * ans for _ in range(3): if b in ''.join(t): return ans ans += 1 t.append(a) return -1 -
func repeatedStringMatch(a string, b string) int { m, n := len(a), len(b) ans := (n + m - 1) / m t := strings.Repeat(a, ans) for i := 0; i < 3; i++ { if strings.Contains(t, b) { return ans } ans++ t += a } return -1 } -
function repeatedStringMatch(a: string, b: string): number { const m: number = a.length, n: number = b.length; let ans: number = Math.ceil(n / m); let t: string = a.repeat(ans); for (let i = 0; i < 3; i++) { if (t.includes(b)) { return ans; } ans++; t += a; } return -1; }