LeetCode重复字符串匹配：求A重复最少次数使B为其子串

嘿，这个问题其实挺常见的，我来给你捋清楚解法思路和代码实现：

问题回顾 #

给定两个字符串A和B，我们需要找到A重复的最小次数，让B成为重复后字符串的子串。如果无论重复多少次都做不到，就返回-1。

举个实际例子：

• 当A="abcd"、B="cdabcdab"时，返回3——因为A重复三次得到abcdabcdabcd，B是它的子串；而A重复两次得到abcdabcd时，B就不是子串。

注意：A和B的长度范围是1到10000，所以解法得兼顾效率和正确性。

核心解法思路 #

首先我们得明确一个基础的重复次数q：这是满足「A重复q次后的长度≥B的长度」的最小整数。计算方式很简单，用B的长度除以A的长度，向上取整就行。在代码里我们可以用(len(B) + len(A) - 1) // len(A)来实现，避免浮点运算的误差。

为什么要先算q？因为如果A重复q次都装不下B，那肯定不可能包含B。但装得下也不一定包含，比如上面的例子里q=2，A重复2次的长度和B一样，但B不是它的子串。这时候我们只需要再试一次q+1次的情况就够了——因为A重复q+1次后，相当于在q次的基础上多了一个完整的A，这时候B的开头可以从A的后半段开始，结尾延伸到下一个A的前半段，覆盖了所有可能的交叉匹配情况。

如果A重复q次或者q+1次都不包含B，那不管再重复多少次都没用了，直接返回-1就行。

代码实现（Python） #

def repeatedStringMatch(A: str, B: str) -> int:
    # 计算最小的q值：满足len(A*q) >= len(B)的最小整数
    q = (len(B) + len(A) - 1) // len(A)
    
    # 先检查q次重复的情况
    if B in A * q:
        return q
    # 再检查q+1次重复的情况（覆盖交叉匹配的可能）
    if B in A * (q + 1):
        return q + 1
    # 两种情况都不满足，返回-1
    return -1

关键细节解释 #

1. q的计算方式：(len(B) + len(A) - 1) // len(A)是Python里实现向上取整的常用技巧，比如len(B)=8、len(A)=4时，(8+4-1)//4=11//4=2；len(B)=9、len(A)=4时，(9+4-1)//4=12//4=3，完全符合我们的需求。
2. 为什么只需要检查q和q+1：假设A重复q+2次才能包含B，那B的长度必然小于等于len(A*(q+2))，但此时B其实也应该能在A*(q+1)里找到——因为A*(q+2)只是比A*(q+1)多了一个A，而B的长度已经小于等于len(A*(q+1))，如果在更长的字符串里能找到，那在A*(q+1)里也一定能找到（因为B的起始位置不可能落在最后一个A上，否则长度会超过len(A*(q+1))）。所以最多检查到q+1次就够了。
3. 边界情况处理：
   • 如果B本身就是A的子串，比如A="abc"、B="ab"，那q=1，直接返回1；
   • 如果A比B短但需要交叉匹配，比如A="abc"、B="cab"，q=1（因为len(B)=3=len(A)），A1不包含B，但A2="abcabc"包含B，返回2；
   • 如果B包含A没有的字符，比如A="abc"、B="abd"，不管重复多少次都不可能，代码会返回-1。

内容的提问来源于stack exchange，提问作者Geeek