[LeetCode每日一题] |686.重复叠加字符串匹配

题目链接

https://leetcode-cn.com/problems/repeated-string-match

题目描述

题目难度：中等

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

注意：字符串 "abc" 重复叠加 0 次是 ""，重复叠加 1 次是 "abc"，重复叠加 2 次是 "abcabc"。

解题思路

Python里字符串匹配是很容易的，直接调用 x.find(y)即可找到 y在 x中的位置。

但本题中需要把 a重复叠加若干遍后，才 有可能 包含子串 b（也可能永远都不包含）,因此不能无限的堆叠 a，而是要找到一个合理的上界 k ，使得 如果 a重复叠加 k 次后 b仍不是其子串，则无论叠加多少次， b永远不会是其子串。

因此这里的核心就是确定这个上界 k，此处应该有一个GIF图，就很好理解了，但由于GIF制作有（不）些（会）麻（制）烦（做），因此直接给出结论：

可以使 len(a) * k >= len(a) + len(b)成立的 k 都是可行的。

所以只要重复堆叠 a，直到其长度大于 len(a) + len(b)，然后调用
.find()即可找到 b在堆叠字符串中的位置，通过这个位置可以判断最少堆叠多少次后可以包含 b。

# Python3
class Solution:
    def repeatedStringMatch(self, a: str, b: str) -> int:
        res = len(b) // len(a) + 1
        temp = ''
        for _ in range(res):
            temp += a
        temp += a
        # 提交后发现使用temp.find(b)方法需要耗时84ms，
        # 而下面这种直接遍历只需要40ms，因此改用遍历
        for i in range(len(temp) - len(b) + 1):
            if b == temp[i: i + len(b)]:
                x, y = divmod(i + len(b), len(a))
                if y > 0:
                    x += 1
                return x
        return -1
            return x
        return -1