Python - N个重复K个字符的非重叠出现

本文将使用Python查找N个重复K个字符的非重叠出现。在使用Python处理字符串时，这类问题非常常见。

理解问题

问题在于查找N个重复K个字符的非重叠出现。简单来说，我们会得到一个字符串，在这个字符串中会有一些重复的字符，所以我们必须找出特定字符的出现次数并显示其计数。这里N是给定输入字符串中的任何字符，K是字符N的计数。

上述问题的逻辑

为了解决这个问题，我们将使用循环遍历给定的字符串，然后检查N和K的值。并检查包含N（K次）的子字符串。并使用对象来存储这些出现的计数。

算法

  • 步骤1 - 首先定义一个名为non_overlapping()的函数，在这个函数中，我们将传递三个参数n、k和the_str。这里n是字符，k是n的字符计数，the_str是输入字符串

  • 步骤2 - 初始化一个名为result的变量，该变量将用于跟踪非重叠出现的计数。

  • 步骤3 - 接下来，我们将使用分隔符'B'分割给定的字符串the_str。这将创建一个子字符串列表。

  • 步骤4 - 将在一个循环中遍历列表中的每个子字符串。

  • 步骤5 - 对于每个子字符串，我们将使用lambda函数中的filter函数过滤字符N的出现。这里lambda函数将用于检查每个字符是否等于K。

  • 步骤6 - 现在将过滤后的结果转换为列表，然后计算长度。

  • 步骤7 - 然后，我们将长度除以K以检查当前子字符串中非重叠出现的次数。

  • 步骤8 - 之后，将count的值添加到result变量中。

  • 步骤9 - 当迭代过程结束时，非重叠出现的最终计数将保存在result变量中。

示例

Open Compiler
# Define the function
def non_overlapping(n, k, the_str):
   # Initialize the result object
   result = 0
   # Traverse the string
   for sub in the_str.split('B'):
      result += len(list(filter(lambda x: x == k, sub))) // n
   return result

the_str = 'AABBCCDDAABBGGHH'
K = "A"
N = 2  
print("The Input String is : " + str(the_str))
Output = non_overlapping(N, K, the_str)
print("Non-Overlapping occurrences result : " + str(Output))

输出

The Input String is : AABBCCDDAABBGGHH
Non-Overlapping occurrences result : 2

复杂度

查找N个重复K个字符的非重叠出现的的时间复杂度为O(m)，这里m是给定输入字符串的长度。对于每次迭代，我们都过滤了字符A的出现次数，并计算了A出现K=2次的次数。

Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.

结论

我们已经使用Python实现了查找N个重复K个字符的非重叠出现的解决方案。我们使用了一种非常直接的方法来解决这个问题，时间复杂度为O(m)。

更新于：2023年10月17日

68 次浏览

开启你的职业生涯

完成课程获得认证

开始
广告