466. 统计重复个数

约定不等于承诺〃 2023-05-21 13:53 3阅读 0赞

**题目描述：**

由 `n` 个连接的字符串 `s` 组成字符串 `S`，记作 `S = [s,n]`。例如，`["abc",3]=“abcabcabc”`。

如果我们可以从 `s2` 中删除某些字符使其变为 `s1`，则称字符串 `s1` 可以从字符串 `s2` 获得。例如，根据定义，`"abc"` 可以从 `“abdbec”` 获得，但不能从 `“acbbe”` 获得。

现在给你两个非空字符串 `s1` 和 `s2`（每个最多 100 个字符长）和两个整数 `0 ≤ n1 ≤ 10^6 和 1 ≤ n2 ≤ 10^6`。现在考虑字符串 `S1` 和 `S2`，其中 `S1=[s1,n1] 、S2=[s2,n2]` 。

请你找出一个可以满足使`[S2,M]` 从 `S1` 获得的最大整数 `M` 。

**示例：**

输入：
    s1 ="acb",n1 = 4
    s2 ="ab",n2 = 2
    返回：
    2

--------------------

**解题思路1:**(超出时间限制)

将S1的长度大于S2的长度，根据题目的意思是需要在S1中查找有多少个S2。因此设置一个计数值k，当计数值k满足S2的长度时，统计个数的m值加1，然后k值重新归零即可

--------------------

**代码1：**

class Solution(object):
        def getMaxRepetitions(self, s1, n1, s2, n2):
            S1 = s1 * n1
            S2 = s2 * n2
            m, k, i, j = 0, 0, 0, 0
    
            while i < len(S1):
                if S1[i] == S2[j]:
                    j += 1
                    i += 1
                    k += 1
                else:
                    i += 1
                if k == len(S2):
                    m += 1
                    j = 0
                    k = 0
            return m

--------------------

**解题思路2:**

来源于：[力扣官方][Link 1]

--------------------

**代码2：**

class Solution:
        def getMaxRepetitions(self, s1, n1, s2, n2):
            if n1 == 0:
                return 0
            s1cnt, index, s2cnt = 0, 0, 0
            recall = dict()
            while True:
                # 我们多遍历一个 s1，看看能不能找到循环节
                s1cnt += 1
                for ch in s1:
                    if ch == s2[index]:
                        index += 1
                        if index == len(s2):
                            s2cnt, index = s2cnt + 1, 0
                # 还没有找到循环节，所有的 s1 就用完了
                if s1cnt == n1:
                    return s2cnt // n2
                # 出现了之前的 index，表示找到了循环节
                if index in recall:
                    s1cnt_prime, s2cnt_prime = recall[index]
                    # 前 s1cnt' 个 s1 包含了 s2cnt' 个 s2
                    pre_loop = (s1cnt_prime, s2cnt_prime)
                    # 以后的每 (s1cnt - s1cnt') 个 s1 包含了 (s2cnt - s2cnt') 个 s2
                    in_loop = (s1cnt - s1cnt_prime, s2cnt - s2cnt_prime)
                    break
                else:
                    recall[index] = (s1cnt, s2cnt)
    
            # ans 存储的是 S1 包含的 s2 的数量，考虑的之前的 pre_loop 和 in_loop
            ans = pre_loop[1] + (n1 - pre_loop[0]) // in_loop[0] * in_loop[1]
            # S1 的末尾还剩下一些 s1，我们暴力进行匹配
            rest = (n1 - pre_loop[0]) % in_loop[0]
            for i in range(rest):
                for ch in s1:
                    if ch == s2[index]:
                        index += 1
                        if index == len(s2):
                            ans, index = ans + 1, 0
            # S1 包含 ans 个 s2，那么就包含 ans / n2 个 S2
            return ans // n2

--------------------

**题目来源：**

[https://leetcode-cn.com/problems/count-the-repetitions][https_leetcode-cn.com_problems_count-the-repetitions]

[Link 1]: https://leetcode-cn.com/problems/count-the-repetitions/solution/tong-ji-zhong-fu-ge-shu-by-leetcode-solution/
[https_leetcode-cn.com_problems_count-the-repetitions]: https://leetcode-cn.com/problems/count-the-repetitions