Leetcode

Repeated String Match

May 26, 2022 by aAshish

  • Time:O(|\texttt{A}| + |\texttt{B}|)
  • Space:O(|\texttt{A}| + |\texttt{B}|)

C++

 
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;
  }
};

JAVA

 
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;
  }
}

Python

 
class Solution:
  def repeatedStringMatch(self, a: str, b: str) -> int:
    n = ceil(len(b) / len(a))
    s = a * n
    if b in s:
      return n
    if b in s + a:
      return n + 1
    return -1