leetcode

686-重复叠加字符串匹配

给定两个字符串 A 和 B, 寻找重复叠加字符串A的最小次数，使得字符串B成为叠加后的字符串A的子串，如果不存在则返回 -1。
举个例子，A = “abcd”，B = “cdabcdab”。
答案为 3， 因为 A 重复叠加三遍后为 “abcdabcdabcd”，此时 B 是其子串；A 重复叠加两遍后为”abcdabcd”，B 并不是其子串。

注意:

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
     public int repeatedStringMatch(String A, String B) {
        if (A.length() >= B.length()) {
            if (A.contains(B))  // 注释1
                return 1;
        }
        for (int s = 0; s < A.length(); s++) { 
            if (A.charAt(s) == B.charAt(0)) {  // 注释2
                int ret = 1;
                boolean flag = false;
                int index = s;
                for (int i = 0; i < B.length(); i++) {  // 注释3
                    if (index == A.length()) {
                        index = 0;
                        ret += 1;  // 注释5
                    }
                    if (B.charAt(i) == A.charAt(index)) {
                        index++;
                        continue;
                    }
                    flag = true;  // 注释4
                    break;
                }
                if (flag)
                    continue;
                return ret;
            }
        }
        return -1;
    }
}

代码中注释对应语句

  • 注释1.如果是子串直接返回1.
  • 注释2.遍历A字符串寻找与B字符串开头一致的字符.
  • 注释3.遍历B字符串,然后对位到A字符串.
  • 注释4.任意不一样,则该情况走不通.
  • 注释5.如果索引超过A字符串长度,则需要叠加数+1.