Skip to content

Latest commit

 

History

History
142 lines (107 loc) · 3.43 KB

File metadata and controls

142 lines (107 loc) · 3.43 KB

English Version

题目描述

给定两个字符串 ab,寻找重复叠加字符串 a 的最小次数,使得字符串 b 成为叠加后的字符串 a 的子串,如果不存在则返回 -1

注意:字符串 "abc" 重复叠加 0 次是 "",重复叠加 1 次是 "abc",重复叠加 2 次是 "abcabc"

 

示例 1:

输入:a = "abcd", b = "cdabcdab"
输出:3
解释:a 重复叠加三遍后为 "abcdabcdabcd", 此时 b 是其子串。

示例 2:

输入:a = "a", b = "aa"
输出:2

示例 3:

输入:a = "a", b = "a"
输出:1

示例 4:

输入:a = "abc", b = "wxyz"
输出:-1

 

提示:

  • 1 <= a.length <= 104
  • 1 <= b.length <= 104
  • ab 由小写英文字母组成

解法

新串由 a 通过重复最小 ans 次得来,假设新串包含子字符串 b,那么新串的起始匹配位置一定不超过 a。

Python3

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

Java

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

C++

class Solution {
public:
    int repeatedStringMatch(string a, string b) {
        int m = a.size(), n = b.size();
        int ans = (n + m - 1) / m;
        string t = "";
        for (int i = 0; i < ans; ++i) t += a;
        for (int i = 0; i < 3; ++i) {
            if (t.find(b) != -1) return ans;
            ++ans;
            t += a;
        }
        return -1;
    }
};

Go

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
}

...