TNotes.leetcode

Appearance

0686. 重复叠加字符串匹配【中等】

0686. 重复叠加字符串匹配【中等】 ​

1. 📝 题目描述 ​

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

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

示例 1：

txt
输入：a = "abcd", b = "cdabcdab"
输出：3

解释：a 重复叠加三遍后为 "abcdabcdabcd", 此时 b 是其子串。

示例 2：

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

示例 3：

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

示例 4：

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

提示：

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

2. 🎯 s.1 - 字符串匹配 ​

c
int repeatedStringMatch(char* a, char* b) {
    int aLen = strlen(a), bLen = strlen(b);
    int count = 1;
    int rLen = aLen;
    char* repeated = (char*)malloc(aLen * (bLen / aLen + 3) + 1);
    strcpy(repeated, a);
    while (rLen < bLen) {
        strcat(repeated, a);
        rLen += aLen;
        count++;
    }
    if (strstr(repeated, b)) {
        free(repeated);
        return count;
    }
    strcat(repeated, a);
    count++;
    if (strstr(repeated, b)) {
        free(repeated);
        return count;
    }
    free(repeated);
    return -1;
}
js
/**
 * @param {string} a
 * @param {string} b
 * @return {number}
 */
var repeatedStringMatch = function (a, b) {
  let repeated = a
  let count = 1
  while (repeated.length < b.length) {
    repeated += a
    count++
  }
  if (repeated.includes(b)) return count
  repeated += a
  count++
  if (repeated.includes(b)) return count
  return -1
}
py
class Solution:
    def repeatedStringMatch(self, a: str, b: str) -> int:
        count = -(-len(b) // len(a))  # ceil division
        repeated = a * count
        if b in repeated:
            return count
        if b in repeated + a:
            return count + 1
        return -1
  • 时间复杂度：O(n+m)，其中 n 和 m 分别是字符串 a 和 b 的长度
  • 空间复杂度：O(n+m)，其中 n 和 m 分别是字符串 a 和 b 的长度，主要来自构造重复后的字符串

算法思路：

  • 将 a 重复叠加直到长度 ≥ b，然后检查 b 是否为子串
  • 若不是，再多加一次 a（处理跨边界的情况）
  • 仍不是则返回 -1

3. 🎯 s.2 - 手写 KMP ​

c
int* buildNext(char* pattern, int patternLen) {
    int* next = (int*)calloc(patternLen, sizeof(int));

    for (int i = 1, j = 0; i < patternLen; i++) {
        while (j > 0 && pattern[i] != pattern[j])
            j = next[j - 1];
        if (pattern[i] == pattern[j])
            j++;
        next[i] = j;
    }

    return next;
}

bool kmpSearchRepeated(char* a, char* pattern, int repeatCount, int* next) {
    int aLen = strlen(a);
    int patternLen = strlen(pattern);
    int totalLen = aLen * repeatCount;

    for (int i = 0, j = 0; i < totalLen; i++) {
        char ch = a[i % aLen];

        while (j > 0 && ch != pattern[j])
            j = next[j - 1];
        if (ch == pattern[j])
            j++;
        if (j == patternLen)
            return true;
    }

    return false;
}

int repeatedStringMatch(char* a, char* b) {
    int aLen = strlen(a);
    int bLen = strlen(b);
    int need = (bLen + aLen - 1) / aLen;
    int* next = buildNext(b, bLen);

    if (kmpSearchRepeated(a, b, need, next)) {
        free(next);
        return need;
    }
    if (kmpSearchRepeated(a, b, need + 1, next)) {
        free(next);
        return need + 1;
    }

    free(next);
    return -1;
}
js
/**
 * @param {string} a
 * @param {string} b
 * @return {number}
 */
var repeatedStringMatch = function (a, b) {
  const aLen = a.length
  const bLen = b.length
  const need = Math.ceil(bLen / aLen)
  const next = buildNext(b)

  if (kmpSearchRepeated(a, b, need, next)) return need
  if (kmpSearchRepeated(a, b, need + 1, next)) return need + 1

  return -1
}

function buildNext(pattern) {
  const next = new Array(pattern.length).fill(0)

  for (let i = 1, j = 0; i < pattern.length; i++) {
    while (j > 0 && pattern[i] !== pattern[j]) j = next[j - 1]
    if (pattern[i] === pattern[j]) j++
    next[i] = j
  }

  return next
}

function kmpSearchRepeated(a, pattern, repeatCount, next) {
  const totalLen = a.length * repeatCount

  for (let i = 0, j = 0; i < totalLen; i++) {
    const ch = a[i % a.length]

    while (j > 0 && ch !== pattern[j]) j = next[j - 1]
    if (ch === pattern[j]) j++
    if (j === pattern.length) return true
  }

  return false
}
py
class Solution:
    def repeatedStringMatch(self, a: str, b: str) -> int:
        a_len = len(a)
        b_len = len(b)
        need = (b_len + a_len - 1) // a_len
        next_arr = self._build_next(b)

        if self._kmp_search_repeated(a, b, need, next_arr):
            return need
        if self._kmp_search_repeated(a, b, need + 1, next_arr):
            return need + 1

        return -1

    def _build_next(self, pattern: str) -> list[int]:
        next_arr = [0] * len(pattern)

        j = 0
        for i in range(1, len(pattern)):
            while j > 0 and pattern[i] != pattern[j]:
                j = next_arr[j - 1]
            if pattern[i] == pattern[j]:
                j += 1
            next_arr[i] = j

        return next_arr

    def _kmp_search_repeated(
        self, a: str, pattern: str, repeat_count: int, next_arr: list[int]
    ) -> bool:
        total_len = len(a) * repeat_count
        j = 0

        for i in range(total_len):
            ch = a[i % len(a)]
            while j > 0 and ch != pattern[j]:
                j = next_arr[j - 1]
            if ch == pattern[j]:
                j += 1
            if j == len(pattern):
                return True

        return False
  • 时间复杂度：O(n+m)，其中 n 和 m 分别是字符串 a 和 b 的长度，构建前缀函数需要 O(m)，匹配时最多线性扫描长度为 m+n 的候选区间
  • 空间复杂度：O(m)，只需要为模式串 b 维护前缀函数数组

算法思路：

  • 思路同 s.1
  • 结构不变，差异在于把 includes 替换成 KMP 搜索，匹配过程从黑盒变成白盒，时间复杂度从依赖引擎保证变成明确 O(n+m)

Discussions