[LeetCode] 686. Repeated String Match

Given two strings A and B, find the minimum number of times A has to be repeated such that B is a substring of it. If no such solution, return -1.

For example, with A = "abcd" and B = "cdabcdab".

Return 3, because by repeating A three times (“abcdabcdabcd”), B is a substring of it; and B is not a substring of A repeated two times ("abcdabcd").

Note:
The length of A and B will be between 1 and 10000.

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

举个例子，A = "abcd"，B = "cdabcdab"。

答案为 3，因为 A 重复叠加三遍后为 “abcdabcdabcd”，此时 B 是其子串；A 重复叠加两遍后为"abcdabcd"，B 并不是其子串。

注意:

A 与 B 字符串的长度在1和10000区间范围内。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/repeated-string-match
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

重复叠加字符串匹配。

很简单的题目，比较直观的思路就是不断让A重复自己，看看是否能包含B。所以原则上如果A的长度大于等于B的时候，就可以停止了。但是这个题有一个坑，就比如题目中给的这个例子，当A重复两遍，虽然长度跟B相同但是其实此时是无法满足题意的。所以需要多重复一次，如果再重复一次之后仍然不满足题意，则返回-1。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     public int repeatedStringMatch(String A, String B) {
 3         int count = 0;
 4         StringBuilder sb = new StringBuilder();
 5         while (sb.length() < B.length()) {
 6             sb.append(A);
 7             count++;
 8         }
 9         if (sb.toString().contains(B)) {
10             return count;
11         }
12         if (sb.append(A).toString().contains(B)) {
13             return ++count;
14         }
15         return -1;
16     }
17 }

一个更快的Java实现，用到了string.lastIndexOf()

 1 class Solution {
 2     public int repeatedStringMatch(String a, String b) {
 3         int i = 1;
 4         StringBuilder sb = new StringBuilder(a);
 5         while (sb.length() < b.length()) {
 6             sb.append(a);
 7             i++;
 8         }
 9         if (sb.toString().lastIndexOf(b) != -1) {
10             return i;
11         }
12         if (sb.append(a).toString().lastIndexOf(b) != -1) {
13             return i + 1;
14         }
15         return -1;
16     }
17 }