统计列表中允许单个字符不匹配的字符串出现次数

我有一个字符串列表：

my_list = 'AAA AAA BBB BBB DDD DDD DDA'.split()
my_list
# 输出: ['AAA', 'AAA', 'BBB', 'BBB', 'DDD', 'DDD', 'DDA']

需要统计列表中每个元素的出现次数，但允许将仅有单个字符不匹配的字符串视为同一字符串统计。我平时用my_list.count('AAA')做精确匹配统计，但不知道怎么实现单字符不匹配的判断逻辑。试过两层for循环两两比较累加，但时间复杂度是O(n²)，效率太低。

期望输出：

AAA 2
BBB 2
DDD 3
DDA 3

最优解决方案：并查集（Union-Find） #

用并查集可以高效将符合条件的字符串归为同一组，之后统计每组的元素数量，时间复杂度可优化至O(n*k)（k为字符串长度），远优于O(n²)。

实现步骤 #

1. 用并查集管理唯一字符串的分组，支持快速合并和查找根节点。
2. 计算等长字符串的汉明距离（不同字符的数量），距离为1时合并两组。
3. 遍历原列表，每个元素通过查找根节点获取对应组的总数量。

代码实现 #

class UnionFind:
    def __init__(self, elements):
        self.parent = {elem: elem for elem in elements}
        self.size = {elem: 1 for elem in elements}
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路径压缩
        return self.parent[x]
    
    def union(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root == y_root:
            return
        # 按大小合并，优化后续查找效率
        if self.size[x_root] < self.size[y_root]:
            x_root, y_root = y_root, x_root
        self.parent[y_root] = x_root
        self.size[x_root] += self.size[y_root]

# 计算两个等长字符串的汉明距离（不同字符的数量）
def hamming_distance(s1, s2):
    return sum(c1 != c2 for c1, c2 in zip(s1, s2))

my_list = 'AAA AAA BBB BBB DDD DDD DDA'.split()
unique_strings = list(set(my_list))

# 初始化并查集
uf = UnionFind(unique_strings)

# 遍历所有唯一字符串对，合并符合条件的组
for i in range(len(unique_strings)):
    s1 = unique_strings[i]
    for j in range(i + 1, len(unique_strings)):
        s2 = unique_strings[j]
        if len(s1) == len(s2) and hamming_distance(s1, s2) == 1:
            uf.union(s1, s2)

# 统计每个元素对应的组大小
count_result = {}
for s in my_list:
    root = uf.find(s)
    count_result[s] = uf.size[root]

# 按字符串排序输出
for s in sorted(count_result.keys()):
    print(f"{s} {count_result[s]}")

输出结果 #

AAA 2
BBB 2
DDD 3
DDA 3

额外说明 #

如果你的字符串存在长度不同的情况，需要把汉明距离替换为编辑距离（Levenshtein距离），判断编辑距离是否≤1。编辑距离可以用动态规划实现，短字符串场景下开销可忽略。

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