[数据结构与算法]leetcode:686. 重复叠加字符串匹配

题目

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/repeated-string-match/

给定两个字符串 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 <= 104
1 <= b.length <= 104
a 和 b 由小写英文字母组成

解法

首先， 如果 b 中有不在 a 里面的字符，直接就可以返回 -1 了。

然后，需要计算 a 需要重复多少次才能完全包含 b。

假设 b 的长度是 a 的 x 倍，主要有以下三种情况，分别举例说明：

• a 重复 x 次后正好等于 b，比如 a=“ab”, b=“abab”，a 只需要重复 2 次即可；

• a 重复 x 次后无法包含 b，比如 a=“ab”, b=“ababa”，a 需要重复 3次才可以，也就是 x+1 次；

• a 重复 x+1 次后也无法包含 b，比如 a=“abc”, b=“cabcabca”，a 需要重复 4次才可以，也就是 x+2 次；
  上面三种情况已经可以包含所有的情况了，因为中间一部分肯定是跟 a 重复 x 次后完全匹配的，然后，两头需要 a 各再重复一次。
  最后，如果 a 重复了 x+2 次都无法包含 b，那么，再重复更多次也不行，直接返回 -1。

• python

 class Solution:

    def repeatedStringMatch(self, a: str, b: str) -> int:
        for s in b:
            if s not in a:
                return -1

        c = len(b) // len(a)

        sb = a * c
        for i in range(3):
            if b in sb:
                return c+i
            sb += a
        return -1

• c++

class Solution {
public:
    int repeatedStringMatch(string a, string b) {
        int len_a = a.length();
        int len_b = b.length();
        string::size_type idx;
        for(int i=0; i< len_b; i++)
        {
            char s = b[i];
            idx = a.find(s);
            if(idx == string::npos)
            {
                return -1;
            }
        }

        int x = len_b / len_a;
        string new_a;
        for(int i=0; i<x; i++)
        {
            new_a += a;
        }

        for(int i=0; i<3; i++)
        {
            idx = new_a.find(b);
            if (idx != string::npos)
            {
                return x+i;
            }
            new_a += a;
        }
        return -1;
    }
};

复杂度分析

• 时间复杂度：
  • $O(n+m)$
• 空间复杂度
  • $O(n??m/n?)$