686. 重复叠加字符串匹配
给定两个字符串 a 和 b,寻找重复叠加字符串 a 的最小次数,使得字符串 b 成为叠加后的字符串 a 的子串,如果不存在则返回 -1。
注意:字符串 “abc” 重复叠加 0 次是 “”,重复叠加 1 次是 “abc”,重复叠加 2 次是 “abcabc”。
public class Solution { public int RepeatedStringMatch(string a, string b) { string A = a; int ans = 1; int maxLength = 2*a.Length + b.Length; while(a.Length <= maxLength) { if(a.IndexOf(b) != -1) { return ans; } else { a += A; ans++; } } return -1; } }
我的方法比较暴力
主要是评论区那句长度一定小于2a+b提醒了我
要确定叠加的次数那就要有个上限
什么时候不叠加了呢?
就是叠加后的字符串长度小于2a+b并且包含b
这样就能确保叠加后的字符串有且仅有一个b子串
一次循环下来就可以得出答案了
当然我这样做的效率很低
看了题解才发现大佬们都用的kmp
kmp对现在的我来说属实学不会
寄了寄了