Medium

题目描述

给定两个字符串 a 和 b，返回使字符串 b 成为字符串 a 的子串所需的最少重复次数。如果无论重复多少次都无法使 b 成为 a 的子串，则返回 -1。

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

示例 1：

输入：a = "abcd", b = "cdabcdab"
输出：3
解释：重复 a 三次得到 "abcdabcdabcd"，此时 b 是它的子串。

示例 2：

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

约束条件：

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

解题思路

解题思路

这道题的关键是找到重复字符串 a 的最少次数，使得 b 成为重复后字符串的子串。

方法一：暴力模拟（推荐）

  1. 基本思路：逐步增加重复次数，每次检查 b 是否为当前重复字符串的子串
  2. 优化边界：
    • 最少需要 ceil(len(b) / len(a)) 次重复才可能包含 b
    • 最多只需要检查到 ceil(len(b) / len(a)) + 1 次，因为如果这样都不行，再重复也没意义
  3. 终止条件：当重复字符串长度达到 len(a) + len(b) 时仍未找到，则返回 -1

方法二：字符集检查 + KMP

先检查 b 中的所有字符是否都在 a 中出现过，如果不是则直接返回 -1。然后使用 KMP 算法进行字符串匹配，但实现较复杂。

推荐使用方法一，代码简洁且效率足够。

代码实现

class Solution {
public:
    int repeatedStringMatch(string a, string b) {
        int minRepeats = (b.length() + a.length() - 1) / a.length();
        string repeated = "";
        
        // 构建最少重复次数的字符串
        for (int i = 0; i < minRepeats; i++) {
            repeated += a;
        }
        
        // 检查最少重复次数
        if (repeated.find(b) != string::npos) {
            return minRepeats;
        }
        
        // 再重复一次检查
        repeated += a;
        if (repeated.find(b) != string::npos) {
            return minRepeats + 1;
        }
        
        return -1;
    }
};

class Solution:
    def repeatedStringMatch(self, a: str, b: str) -> int:
        min_repeats = (len(b) + len(a) - 1) // len(a)
        repeated = a * min_repeats
        
        # 检查最少重复次数
        if b in repeated:
            return min_repeats
        
        # 再重复一次检查
        repeated += a
        if b in repeated:
            return min_repeats + 1
        
        return -1

public class Solution {
    public int RepeatedStringMatch(string a, string b) {
        int minRepeats = (b.Length + a.Length - 1) / a.Length;
        string repeated = "";
        
        // 构建最少重复次数的字符串
        for (int i = 0; i < minRepeats; i++) {
            repeated += a;
        }
        
        // 检查最少重复次数
        if (repeated.Contains(b)) {
            return minRepeats;
        }
        
        // 再重复一次检查
        repeated += a;
        if (repeated.Contains(b)) {
            return minRepeats + 1;
        }
        
        return -1;
    }
}

var repeatedStringMatch = function(a, b) {
    const minRepeats = Math.ceil(b.length / a.length);
    let repeated = a.repeat(minRepeats);
    
    // 检查最少重复次数
    if (repeated.includes(b)) {
        return minRepeats;
    }
    
    // 再重复一次检查
    repeated += a;
    if (repeated.includes(b)) {
        return minRepeats + 1;
    }
    
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n+m)n 为字符串 a 的长度，m 为字符串 b 的长度。最多构建长度为 n+m 的字符串并进行一次子串查找
空间复杂度O(n+m)需要存储重复后的字符串，最大长度为 n+m

相关题目