如何从重复的字符串中提取单词

Question

这里我有一个列表中的字符串：

['aaaaaaappppppprrrrrriiiiiilll']

我想在列表中得到单词'april'，但不只是其中一个，而是单词'april'实际出现在字符串中的次数

输出应该类似于：

['aprilaprilapril']

因为“april”这个词在这个字符串中出现了三次

这个词实际上没有出现过三次，所有的角色都出现过。所以我想将这些字符排序为'april'，它们在字符串中出现了多少次

我的想法基本上是从一些随机字符串中提取单词，而不仅仅是提取单词，而是提取字符串中出现的所有单词。每个单词都应该被提取出来，并且单词（字符）应该按照我想要的方式排序

但在这里我有一些恼人的条件；您不能删除列表中的所有元素，然后用单词'april'替换它们（不能用单词'april'替换整个字符串）；只能从字符串中提取'april'，不能替换它们。您也不能删除带有该字符串的列表。想想所有的字符串都是非常重要的数据，我们只需要一些数据，但这些数据必须排序，我们需要删除所有与“数据链”（单词“april”）不匹配的其他数据。但一旦删除整个字符串，就会丢失所有重要数据。你不知道如何制造这些“数据链”中的另一个，所以我们不能仅仅把“四月”这个词放回列表中

如果有人知道如何解决我这个奇怪的问题，请帮助我，我是一个python初学者。谢谢大家!

Answer 1

这是一种更为自然的方法，使用简单的迭代

它的时间复杂度为O（n）。

它使用一个外部循环来迭代搜索键中的字符，然后使用一个内部while循环来消耗搜索字符串中该字符的所有匹配项，同时维护一个计数器。一旦当前字母的所有连续出现都被消耗，它会将minLetterCount更新为其先前值或此新计数的最小值。一旦我们遍历了键中的所有字母，我们将返回这个累积的最小值

def countCompleteSequenceOccurences(searchString, key):
    left = 0
    minLetterCount = 0
    letterCount = 0
    for i, searchChar in enumerate(key):
        while left < len(searchString) and searchString[left] == searchChar:
            letterCount += 1
            left += 1
        
        minLetterCount = letterCount if i == 0 else min(minLetterCount, letterCount)
        letterCount = 0
        
    return minLetterCount

测试：

testCasesToOracles = {
    "aaaaaaappppppprrrrrriiiiiilll": 3,
    "ppppppprrrrrriiiiiilll": 0,
    "aaaaaaappppppprrrrrriiiiii": 0,
    "aaaaaaapppppppzzzrrrrrriiiiiilll": 0,
    "pppppppaaaaaaarrrrrriiiiiilll": 0,
    "zaaaaaaappppppprrrrrriiiiiilll": 3,
    "zzzaaaaaaappppppprrrrrriiiiiilll": 3,
    "aaaaaaappppppprrrrrriiiiiilllzzz": 3,
    "zzzaaaaaaappppppprrrrrriiiiiilllzzz": 3,
}

key = "april"
for case, oracle in testCasesToOracles.items():
    result = countCompleteSequenceOccurences(case, key)
    assert result == oracle

用法：

key = "april"
result = countCompleteSequenceOccurences("aaaaaaappppppprrrrrriiiiiilll", key)
print(result * key)

输出：

aprilaprilapril