Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

686. Repeated String Match

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

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

			


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




			


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




			


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