重复叠加字符串匹配

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

题目说明

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

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

提示：

1 <= a.length <= 10^4
1 <= b.length <= 10^4
a 和 b 由小写英文字母组成

示例

示例 1:

1
2
3

输入：a = "abcd", b = "cdabcdab"
输出：3
解释：a 重复叠加三遍后为 "abcdabcdabcd", 此时 b 是其子串。

示例 2:

1 2	输入：a = "a", b = "aa" 输出：2

示例 3:

1 2	输入：a = "a", b = "a" 输出：1

示例 4:

1 2	输入：a = "abc", b = "wxyz" 输出：-1

笔者理解

此题是一道字符串算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，发现此题中我们只需要知道字符串a重复可能的上界即可，让我们来看看具体如何实现的吧。

实现

class Solution {
    /**
     * 二分查找
     */
    public int repeatedStringMatch(String a, String b) {
        int sizeA = a.length();
        int sizeB = b.length();

        // 最少可能情况 a 包含 b
        int left = 1;
        // 最大可能 a 重复 sizeB / sizeA 次，再在首位各自加一个
        int right = sizeB / sizeA + 2;
        
        StringBuilder sb = new StringBuilder();

        while (left < right) {
            int mid = left + (right - left) / 2;
            sb = new StringBuilder();
            for (int i = 0; i < mid; i++) {
                sb.append(a);
            }
            if (!sb.toString().contains(b)) {
                left = mid + 1;
                sb.append(a);
            }
            else {
                right = mid;
            }
        }

        return !sb.toString().contains(b)? -1: left;
        
    }
}