难度: Medium
给定两个字符串 a 和 b，寻找重复叠加字符串 a 的最小次数，使得字符串 b 成为叠加后的字符串 a 的子串，如果不存在则返回 -1。
注意：字符串 "abc" 重复叠加 0 次是 ""，重复叠加 1 次是 "abc"，重复叠加 2 次是 "abcabc"。
示例 1：
输入：a = "abcd", b = "cdabcdab" 输出：3 解释：a 重复叠加三遍后为 "abcdabcdabcd", 此时 b 是其子串。
示例 2：
输入：a = "a", b = "aa" 输出：2
示例 3：
输入：a = "a", b = "a" 输出：1
示例 4：
输入：a = "abc", b = "wxyz" 输出：-1
提示：
1 <= a.length <= 1041 <= b.length <= 104a 和 b 由小写英文字母组成运行时间: 25 ms
内存: 16.2 MB
class Solution:
def repeatedStringMatch(self, a: str, b: str) -> int:
if b == "":
return 0
if len(a) == 1:
if b.replace(a,"") == "":
return b.count(a)
return -1
if b in a:
return 1
repeat_count = 0
if a in b:
repeat_count = b.count(a)
remain = b.split(a)
for i in range(1,len(remain)-1):
if remain[i] != "":
return -1
# b = b.replace(a,"")
if remain[0] != "":
if a.endswith(remain[0]):
repeat_count +=1
else:
return -1
if remain[-1] != "":
if a.startswith(remain[-1]):
repeat_count +=1
else:
return -1
return repeat_count
if b in (a+a):
return repeat_count + 2
return -1
该题解的思路是通过分情况讨论来解决问题。首先判断特殊情况，如果字符串b为空则返回0；如果字符串a的长度为1，则判断b是否完全由a组成，如果是则返回a在b中出现的次数，否则返回-1。接下来判断一般情况，如果b是a的子串，则直接返回1；如果a是b的子串，则统计a在b中出现的次数，并判断a之间的部分是否为空，以及b的开头和结尾是否能与a匹配，据此计算最小重复次数；如果b是两个a拼接而成的子串，则返回重复次数加2；其他情况返回-1。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def repeatedStringMatch(self, a: str, b: str) -> int:
# 如果字符串b为空，返回0
if b == "":
return 0
# 如果字符串a的长度为1
if len(a) == 1:
# 判断b是否完全由a组成
if b.replace(a,"") == "":
# 返回a在b中出现的次数
return b.count(a)
# 否则返回-1
return -1
# 如果b是a的子串，直接返回1
if b in a:
return 1
repeat_count = 0
# 如果a是b的子串
if a in b:
# 统计a在b中出现的次数
repeat_count = b.count(a)
# 将b按a拆分
remain = b.split(a)
# 判断a之间的部分是否为空
for i in range(1,len(remain)-1):
if remain[i] != "":
return -1
# 判断b的开头是否能与a的结尾匹配
if remain[0] != "":
if a.endswith(remain[0]):
repeat_count +=1
else:
return -1
# 判断b的结尾是否能与a的开头匹配
if remain[-1] != "":
if a.startswith(remain[-1]):
repeat_count +=1
else:
return -1
return repeat_count
# 如果b是两个a拼接而成的子串
if b in (a+a):
return repeat_count + 2
# 其他情况返回-1
return -1
题解中将字符串b为空时返回0的处理方式基本上是符合逻辑的假设。在实际问题场景中，如果b为空，那么不需要重复a就可以匹配到b，因为b没有内容需要被匹配。这可以被视为一种边界条件的合理处理，尽管题目未明确说明，但此处理方式是为了增强算法的鲁棒性。
这种方法在处理b中包含a以外的字符时会失败。例如，如果a是'x'而b是'xy'，此方法会将'x'替换为''，结果是'y'，这不是空字符串，但实际上'a'并不能通过重复匹配整个字符串'b'。因此，这种处理方法只适用于b完全由多个a构成的情况，无法准确处理b包含其他字符的情况。
这种判断没有问题，因为如果b是a的子串，不论b的长度与a的长度如何比较，b已经完全包含在a中了，这意味着不需要额外重复a即可匹配到b。所以，即使b的长度大于a，只要b能作为a的一部分出现，就可以直接返回1。
在题解中，确保拆分后的剩余部分正确地匹配a的开头或结尾是通过明确的字符串操作来完成的。对于剩余部分，算法检查a是否以剩余部分开头（如果剩余部分在b的结尾）或a是否以剩余部分结尾（如果剩余部分在b的开头）。如果这些条件被满足，那么重复次数会相应增加。如果条件不符，就会返回-1，表示无法通过重复a来匹配整个b。这样的处理确保了只有当b的非重复部分能与a的相应部分匹配时，才会计算为有效重复。