跳到主要内容

686.重复叠加字符串匹配

· 阅读需 3 分钟

1、题干​

给定两个字符串 a 和 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

示例 3：

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

示例 4：

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

 

提示：

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

解法1：拼接再判断是否包含​

直接拼接字符串a，并判断a是否包含b，而拼接次数就是题目的解；拼接次数最少是Math.ceil(b.length / a.length)次，如果不行就再加1，再不行就说明解不存在应返回-1。

执行结果​

1.png

代码​

var repeatedStringMatch = function (a, b) {
    const count = Math.ceil(b.length / a.length);
    if (a.repeat(count).includes(b)) return count;
    if (a.repeat(count + 1).includes(b)) return count + 1;
    return -1;
};

解法2：正则替换再判断头尾​

先将字符串b中的a都替换掉并记录匹配数量count，然后再判断字符串b剩下的头和尾是否与a的头尾相同即可：

  • 如果没有头和尾，说明正好需要count个a拼接
  • 如果只有头或尾，说明需要count+1个a拼接
  • 如果有头又有尾，说明需要count+2个a拼接
  • 如果都不是，说明解不存在应返回-1

最开始用的是解法2，踩了2个坑费了不少时间。通过之后想写个正经算法，结果写出了解法1。 再之后。。。放弃了。。。做个API战士吧 😂

执行结果​

1.png

代码​

var repeatedStringMatch = function (a, b) {
    let count = 0;
    b = b.replace(new RegExp(a, 'g'), () => (count++, '$'));

    const s = ''.padEnd(count, '$');
    if (b === s) return count;
    if ((a + s).includes(b) || (s + a).includes(b)) return count + 1;
    if ((a + s + a).includes(b)) return count + 2;
    return -1;
};