如何快速生成ABCDE构成的无3个及以上连续相同字符的10位字符串

原有实现存在的问题 #

• 正则逻辑错误：你使用的正则r'(\w).*\1{3,}'实际匹配规则是「某个字符出现后，间隔任意字符再连续出现3次该字符」，完全不符合「连续3个相同字符」的校验要求，且re.match()仅从字符串开头匹配，会漏判中间、末尾出现的连续相同字符，大量无效字符串会被误判为有效。
• 性能效率低下：通过itertools.product全量生成5^10=9765625个字符串，再逐个校验过滤，大部分算力都浪费在了无效字符串的生成和校验环节。

最优优化方案：回溯法直接生成有效字符串 #

直接在生成阶段就排除不符合规则的字符串，不需要生成全量候选，性能提升最明显：

def generate_valid_strings(target_length: int, char_set: str, max_consecutive: int = 2) -> list[str]:
    result = []
    def backtrack(current_str: list, last_char: str | None, consecutive_cnt: int):
        if len(current_str) == target_length:
            result.append(''.join(current_str))
            return
        for c in char_set:
            if c == last_char:
                if consecutive_cnt < max_consecutive:
                    current_str.append(c)
                    backtrack(current_str, c, consecutive_cnt + 1)
                    current_str.pop()
            else:
                current_str.append(c)
                backtrack(current_str, c, 1)
                current_str.pop()
    backtrack([], None, 0)
    return result

st = 'ABCDE'
valid_strings = generate_valid_strings(10, st)
for s in valid_strings:
    print(s)

备选优化：保留全量生成逻辑，优化校验规则 #

如果不想改动生成逻辑，也可以把正则校验替换为直接遍历判断，性能比正则校验高3~5倍：

import itertools as it

def is_valid(possible_str: str) -> bool:
    for i in range(len(possible_str) - 2):
        if possible_str[i] == possible_str[i+1] == possible_str[i+2]:
            return False
    return True

st = 'ABCDE'
for x in it.product(st, repeat=10):
    out = ''.join(x)
    if is_valid(out):
        print(out)

内容的提问来源于stack exchange，提问作者d1gg3r