Welcome to Subscribe On Youtube
  • /**
    
     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;
    }
    
    

All Problems

All Solutions