/**

 Given two strings A and B, find the minimum number of times A has to be repeated such that B is a substring of it. If no such solution, return -1.

 For example, with A = "abcd" and B = "cdabcdab".

 Return 3, because by repeating A three times (“abcdabcdabcd”), B is a substring of it; and B is not a substring of A repeated two times ("abcdabcd").

 Note:
 The length of A and B will be between 1 and 10000.

 */

public class Repeated_String_Match {

    class Solution {
        public int repeatedStringMatch(String A, String B) {
            int count = 1;
            StringBuilder Acopy = new StringBuilder(A);
            for (; Acopy.length() < B.length(); ) {
                Acopy.append(A);
                count++;
            }
            if (Acopy.indexOf(B) >= 0) {
                return count;
            }
            if (Acopy.append(A).indexOf(B) >= 0) {
                return count+1;
            }

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

// OJ: https://leetcode.com/problems/repeated-string-match/
// Time: O(B * (A + B))
// Space: O(A + B)
// Ref: https://leetcode.com/problems/repeated-string-match/solution/
class Solution {
public:
    int repeatedStringMatch(string a, string b) {
        int k = 1;
        string s = a;
        for (; s.size() < b.size(); ++k) s += a;
        if (s.find(b) != string::npos) return k;
        return (s + a).find(b) != string::npos ? k + 1 : -1;
    }
};

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(object):
    def repeatedStringMatch(self, A, B):
        """
        :type A: str
        :type B: str
        :rtype: int
        """
        na, nb = len(A), len(B)
        times = nb / na + 3
        for i in range(1, times):
            if B in A * i:
                return i
        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;
}

class Solution {
    public int repeatedStringMatch(String A, String B) {
        int lengthA = A.length(), lengthB = B.length();
        StringBuffer sb = new StringBuffer();
        int maxLength = lengthA * 2 + lengthB;
        int repeatTimes = 0;
        while (sb.length() <= maxLength) {
            sb.append(A);
            repeatTimes++;
            if (sb.toString().indexOf(B) >= 0)
                return repeatTimes;
        }
        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;
    }
}

// OJ: https://leetcode.com/problems/repeated-string-match/
// Time: O(B * (A + B))
// Space: O(A + B)
// Ref: https://leetcode.com/problems/repeated-string-match/solution/
class Solution {
public:
    int repeatedStringMatch(string a, string b) {
        int k = 1;
        string s = a;
        for (; s.size() < b.size(); ++k) s += a;
        if (s.find(b) != string::npos) return k;
        return (s + a).find(b) != string::npos ? k + 1 : -1;
    }
};

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(object):
    def repeatedStringMatch(self, A, B):
        """
        :type A: str
        :type B: str
        :rtype: int
        """
        na, nb = len(A), len(B)
        times = nb / na + 3
        for i in range(1, times):
            if B in A * i:
                return i
        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;
}

686 - Repeated String Match

All Problems

All Solutions

Welcome to Subscribe On Youtube

All Problems

All Solutions