Question

686. 重复叠加字符串匹配

English Version

题目描述

给定两个字符串 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 由小写英文字母组成

解法

方法一

class Solution:
  def repeatedStringMatch(self, a: str, b: str) -> int:
    m, n = len(a), len(b)
    ans = ceil(n / m)
    t = [a] * ans
    for _ in range(3):
      if b in ''.join(t):
        return ans
      ans += 1
      t.append(a)
    return -1

class Solution {
  public int repeatedStringMatch(String a, String b) {
    int m = a.length(), n = b.length();
    int ans = (n + m - 1) / m;
    StringBuilder t = new StringBuilder(a.repeat(ans));
    for (int i = 0; i < 3; ++i) {
      if (t.toString().contains(b)) {
        return ans;
      }
      ++ans;
      t.append(a);
    }
    return -1;
  }
}

class Solution {
public:
  int repeatedStringMatch(string a, string b) {
    int m = a.size(), n = b.size();
    int ans = (n + m - 1) / m;
    string t = "";
    for (int i = 0; i < ans; ++i) t += a;
    for (int i = 0; i < 3; ++i) {
      if (t.find(b) != -1) return ans;
      ++ans;
      t += a;
    }
    return -1;
  }
};

func repeatedStringMatch(a string, b string) int {
  m, n := len(a), len(b)
  ans := (n + m - 1) / m
  t := strings.Repeat(a, ans)
  for i := 0; i < 3; i++ {
    if strings.Contains(t, b) {
      return ans
    }
    ans++
    t += a
  }
  return -1
}

function repeatedStringMatch(a: string, b: string): number {
  const m: number = a.length,
    n: number = b.length;
  let ans: number = Math.ceil(n / m);
  let t: string = a.repeat(ans);

  for (let i = 0; i < 3; i++) {
    if (t.includes(b)) {
      return ans;
    }
    ans++;
    t += a;
  }

  return -1;
}