我参加了leetcode的第52场竞赛,但对理解解决方案有困难。问题语句为:
I did Contest 52 of leetcode and I had trouble understanding the solution. The problem statement is:
给出两个字符串A和B,找出必须重复执行A的最小次数,使得B为它的一个子串。如果没有这样的解决方案,则返回-1。
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.
例如,以A = abcd和B = cdabcdab。
For example, with A = "abcd" and B = "cdabcdab.
返回3,因为重复3次( abcdabcdabcd),B是它的>子字符串;而B不是重复2次( abcdabcd)的A的子字符串。
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").
解决方案是:
def repeatedStringMatch(self, A, B): """ :type A: str :type B: str :rtype: int """ times = int(math.ceil(float(len(B)) / len(A))) for i in range(2): if B in (A * (times + i)): return times + i return -1说明来自其中一位合作者的信息:
The explanation from one of the collaborators was:
A必须重复足够的时间,使得其至少与> B一样长(或更多),因此我们可以得出结论:答案的理论下限>是B的长度/
A has to be repeated sufficient times such that it is at least as long as >B (or one more), hence we can conclude that the theoretical lower bound >for the answer would be length of B / length of A.
让x为理论下界,即ceil(len(B)/ len(A))。
Let x be the theoretical lower bound, which is ceil(len(B)/len(A)).
答案n只能是x或x + 1
The answer n can only be x or x + 1
我不明白为什么n只能是x或x + 1,有人可以帮忙吗?
I don't understand why n can only be x or x+1, can someone help?
推荐答案如果 x + 1< n 并且B是A的子字符串,重复了 n 次,并且您已经在其中嵌入了B,那么您可以砍掉A的最后一个副本而不打B(意味着 n 不是最小的),否则A中B的开始是在第一份副本的结尾之后,因此您可以将第一份副本砍掉(并且再次 n 并非最小)。
If x+1 < n and B is a substring of A repeated n times and you've embedded B in it then either you can chop off the last copy of A without hitting B (meaning that n is not minimal) or else the start of B in A is after the end of the first copy so you can chop off the first copy (and again n is not minimal).
因此,如果完全适合,则必须在 x + 1 个副本。仅基于长度,它就不能容纳在< x 个副本。因此,剩下的唯一可能性是 x 和 x + 1 副本。 (示例可以在哪里找到答案)。
Therefore if it fits at all, it must fit within x+1 copies. Based on length alone it can't fit within < x copies. So the only possibilities left are x and x+1 copies. (And examples can be found where each is the answer.)
更多推荐
重复字符串匹配
发布评论