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

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

Answer 2

使用正则表达式怎么样

import re

word = 'april'
text = 'aaaaaaappppppprrrrrriiiiiilll'

regex = "".join(f"({c}+)" for c in word)
match = re.match(regex, text)

if match:
    # Find the lowest amount of character repeats
    lowest_amount = min(len(g) for g in match.groups())
    print(word * lowest_amount)
else:
    print("no match")

产出：

aprilaprilapril

很有魅力

Answer 3

一种方法是使用itertools.groupby将字符单独分组，并使用zip将其解包并迭代n次，因为n是最小组中的字符数（即字符数最少的组）

from itertools import groupby
'aaaaaaappppppprrrrrriiiiiilll'
result = ''
for each in zip(*[list(g) for k, g in groupby('aaaaaaappppppprrrrrriiiiiilll')]):
    result += ''.join(each)

# result = 'aprilaprilapril'    

另一种可能的解决方案是创建一个自定义计数器，用于计算每个唯一的字符序列（请注意，此方法仅适用于Python 3.6+，对于较低版本的Python，不保证字典的顺序）：

def getCounts(strng):
    if not strng:
        return [], 0
    counts = {}
    current = strng[0]
    for c in strng:
        if c in counts.keys():
            if current==c:
                counts[c] += 1
        else:
            current = c
            counts[c] = 1
    return counts.keys(), min(counts.values())

result = ''
counts=getCounts('aaaaaaappppppprrrrrriiiiiilll')
for i in range(counts[1]):
    result += ''.join(counts[0])

# result = 'aprilaprilapril'