不使用Python内置可迭代函数实现字符串列表异位词分组的方案咨询

不用sorted生成异位词唯一key的主流方案为字符频率统计法，核心逻辑是：互为异位词的字符串，每个英文字母的出现次数完全一致，我们可以将字符计数结果作为唯一key存入字典完成分组。

实现代码 #

def groupAnagrams(S):
    res = dict()
    for elem in S:
        elem = elem.lower()
        # 初始化a-z的计数数组，下标0对应a，25对应z
        char_count = [0] * 26
        # 手动遍历统计字符出现次数，无内置可迭代处理函数调用
        for c in elem:
            offset = ord(c) - ord('a')
            char_count[offset] += 1
        # 列表不可哈希，转元组作为字典的key
        key = tuple(char_count)
        if key not in res:
            res[key] = set()
        res[key].add(elem)
    return list(res.values())

方案说明 #

• 时间效率优于排序方案：单字符串处理时间复杂度为O(k)（k为字符串长度），排序方案为O(k log k)，字符串越长性能优势越明显
• 完全满足要求：未使用sorted等内置可迭代处理函数，所有统计逻辑为手动循环实现

可选替代方案 #

如果输入字符串长度普遍较短，也可以使用质数映射乘积法：给a-z每个字母分配一个唯一质数，遍历字符串时将所有字符对应的质数相乘，乘积作为唯一key。该方案的缺点是长字符串场景下乘积数值过大，计算效率会下降。

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