LeetCode-686-重复叠加字符串匹配

2021-12-22

题目

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

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

示例

1
2
3


输入：a = "abcd", b = "cdabcdab"
输出：3
解释：a 重复叠加三遍后为 "abcdabcdabcd", 此时 b 是其子串。

1
2


输入：a = "a", b = "aa"
输出：2

1
2


输入：a = "a", b = "a"
输出：1

1
2


输入：a = "abc", b = "wxyz"
输出：-1

解答

根据题意进行模拟，如果a的长度小于b的长度，newA = newA+a，直到newA.size()>=b.size()结束，在此期间记录加了几次a，然后判断b是否是newA的子串。如果不是子串还要判断newA.size()是否等于b.size()，就像示例 1 一样，虽然 a 叠加两边之后和 b 的 size 一样，b不是a的子串，但是再叠加一次，b就是a的子串了。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


int repeatedStringMatch(string a, string b) {
        string newA = a;
        int ans = 1;
        while (newA.size() < b.size()) {
            ans++;
            cout << "newA.size() = " << newA.size() << endl;
            newA = newA + a;
        }
        string::size_type sizeType = newA.find(b);
        if (sizeType == string::npos) {
            newA += a;
            sizeType = newA.find(b);
            if (sizeType == string::npos) {
                return -1;
            } else {
                return ans + 1;
            }
        }

        return ans;
    }

#中等 #模拟 #字符串