Leetcode 686. 重复叠加字符串匹配

题目描述

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

示例 1:

输入: A = "abcd"，B = "cdabcdab"

输出: 3

解释: 因为 A 重复叠加三遍后为 “abcdabcdabcd”，此时 B 是其子串；A 重复叠加两遍后为"abcdabcd"，B 并不是其子串。

解法

这里以 len(A) 表示字符串 A 的长度

• 当

len(A) > len(B)

时，如果 B 不是 A 或者 A + A 的子串，则返回 -1

• 当

len(A) = len(B)

时，如果 B 不是 A 或者 A + A 的子串，则返回 -1

• 当

len(A) < len(B)

时，不妨设存在

n

，满足

len(n*A) \ge len(B)

，且

len((n-1)*A) < len(B)

，如果 B 不是 n*A 或者 (n+1)*A 的子串，则返回 -1

import math
class Solution:
    def repeatedStringMatch(self, A: str, B: str) -> int:
        if len(set(A))<len(set(B)):
            return -1
        c=math.ceil(len(B)/len(A))
        for i in range(2):
            if B in A*(c+i):
                return c+i
        return -1

若 B 是 重复叠加 A 后的子串，则 A 字符串的字符集应包含 B 字符串的字符集，即

len(set(A)) \ge len(set(B))

。因为

c=math.ceil(len(B)/len(A))

，则有

len(c*A) \ge len(B)

，根据上述情况描述，如果 B 不是 c*A 或者 (c+1)*A 的子串，则返回 -1，否则返回重复次数。