题目

难度：★★☆☆☆
类型：字符串

给定两个字符串 A 和 B, 寻找重复叠加字符串A的最小次数，使得字符串B成为叠加后的字符串A的子串，如果不存在则返回 -1。

举个例子，A = "abcd"，B = "cdabcdab"。

答案为 3， 因为 A 重复叠加三遍后为 “abcdabcdabcd”，此时 B 是其子串；A 重复叠加两遍后为"abcdabcd"，B 并不是其子串。

注意

A 与 B 字符串的长度在1和10000区间范围内。

解答

A_repeat代表A复制r次得到的字符串，我们从1开始逐渐增大r，查看什么时候B能够在A_repeat中。

遍历时重点需要注意：构造出的字符串的最大长度不能超过2*len(A)+len(B)。为什么要选择这个数字？

考虑以下情况：

1. 如果字符串A比字符串B长：
   （1）字符串A本来就包含字符串B，这时A仅复制一遍就找到了，最大长度为len(A)；
   （2）字符串A复制一遍包含字符B，这时A的重复次数为2，遍历控制范围是len(A)2；
   （3）字符串A复制一遍不包含字符B，那么无论复制多少遍也不包含字符B，控制长度在len(A)2即可。

2. 如果字符串A比字符串B短，我们将字符串A复制到刚好大于字符串B的长度，长度控制为不小于len(B)时跳出循环。

3. 以上两种情况取最大值，求和即可：len(A)*2+len(B)。

class Solution:
    def repeatedStringMatch(self, A: str, B: str) -> int:

        A_repeat, r = A, 1
        while len(A_repeat) < 2 * len(A) + len(B):
            if B in A_repeat:
                return r
            A_repeat, r = A_repeat + A, r + 1

        return -1

如有疑问或建议，欢迎评论区留言~