Skip to content

686. Repeated String Match

  • Time: $O(|\texttt{a}| + |\texttt{b}|)$
  • Space: $O(|\texttt{a}| + |\texttt{b}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
 public:
  int repeatedStringMatch(string a, string b) {
    const int n = ceil((double)b.length() / a.length());
    string s;

    for (int i = 0; i < n; ++i)
      s += a;

    if (s.find(b) != string::npos)
      return n;
    if ((s + a).find(b) != string::npos)
      return n + 1;
    return -1;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
  public int repeatedStringMatch(String A, String B) {
    final int n = (int) Math.ceil((double) B.length() / (double) A.length());
    final String s = String.join("", Collections.nCopies(n, A));
    if (s.contains(B))
      return n;
    if ((s + A).contains(B))
      return n + 1;
    return -1;
  }
}

1
2
3
4
5
6
7
8
9
class Solution:
  def repeatedStringMatch(self, a: str, b: str) -> int:
    n = math.ceil(len(b) / len(a))
    s = a * n
    if b in s:
      return n
    if b in s + a:
      return n + 1
    return -1