【快乐水题】686. 重复叠加字符串匹配

原题：

力扣链接:686. 重复叠加字符串匹配

题目简述：

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

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

解题思路

审题提炼

1.匹配子串，使用find函数实现子串查找；
2.然后循环叠加，找到退出循环的判据（这步倒腾很久都没倒腾出来，哎，提交了好几次都失败了），实现找不到子串的情况的退出；

波折心路（地铁上手机刷题）：

1.自己的退出循环的判据一直错，捣鼓半天一直错，最后没办法，只能直奔题解区了。
2.看了官方的题解云里雾里，和我的方法有出入啊，于是又翻了翻，最终找到了和我思路类似的大佬的题解。看了大佬的题解豁然开朗，果断运行一波，如丝般润滑。
3.奉上大佬链接：
关键是找到循环终止条件

如果n个A字符串能包含B字符串，可能有几种情况：
1、A = “ab”, B = “abab”,循环n个A，刚好包含B；
2、A = “ab”, B = “ababa”,那么需要循环n + 1次；
3、A = “ab”, B = “babab”，那么需要循环n + 1次；
4、A = “ab”, B = “bababa”，那么需要循环n + 1次；
如果B不满足以上情况，A再怎么循环也是白搭，比如，A = “ab”, B = “bababb”，循环多少次都只是浪费。
因此，如果B能够在A的N次循环中被找到，最多只需要循环n+2次。循环终止条件就是累积的字符串长度 > (n + 2) * sizeA = (sizeB/sizeA + 2) * sizeA= sizeB + 2*sizeA.

4.over;

C++代码：

class Solution { public:int repeatedStringMatch(string a, string b) {int na = a.size();int nb = b.size();string aa;int naa = 0;int i = 0;while(1){if(aa.find(b) != -1){return i;}i++;aa += a;naa =aa.size();if(naa > 2*na + nb)return -1;} return -1;} };

力扣结果展示：

总结

以上是生活随笔为你收集整理的【快乐水题】686. 重复叠加字符串匹配的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。