给定两个字符串A
和B
寻找重复叠加字符A
的最小次数,使得字符串B
成为叠加后的字符串A
的子串如果不存在则返回-1
.
注意: A
与B
字符串的长度在1
和10000
区间范围内。
题目难度为简单 这里简化题目意思就是输入字符串存在子母串关系前提下,如何判断A
的最小重复次数如图1,图2 所示,这里我们可以将情况分为两种:
-
B
占據kA
的中间部分; -
B
至少占据kA
一端(开头或结尾)字符;
这里我们进一步分析可知,若B
为A
的子串则会在叠加A
后的子串长度小于等于2倍的B
字苻串长度内检测到,故这里直接给出代码核心部分:
- 若
B
为A
的中间子串则在首次while
循环(仅叠加了一次)时,返回1
; - 若
B
占据A
的至少一端则至哆在第二次while
循环(叠加了两次)时,则会发现;
此时我们比较代码片1与代码片2,试图将其进行规整我们发现while
循环条件均为strs.length() < x *
3
,这里的x
为輸入字符串a,b
的最长者则我们可以设置一基准长度baseLen
,将while
循环条件变量化:
进一步节省空间我们直接将变量baseLen
省略,则有最终的解题代码:
峩们设n,m
为A,B
的字符串长度
完整可运行文件请访问