将字符串数组排序后按字母异位词分组为对象数组的技术需求

需求说明 #

给定输入数组：

input = ['abc', 'def','ghi', 'bac', 'fed', 'hgi', 'cab', 'edf', 'igh']

需对数组中的字符串进行分组，将互为字母异位词（即字符组成相同、顺序不同的字符串）的元素归为一组，最终输出格式为：

output = [{'abc', 'bac', 'cab'}, {'def', 'edf', 'fed'}, {'ghi', 'hgi', 'igh'}]

实现思路与代码 #

核心思路是利用排序后的字符序列作为唯一标识：字母异位词排序后的字符序列完全相同，以此为键可以快速分组。以下是Python实现代码：

input_arr = ['abc', 'def','ghi', 'bac', 'fed', 'hgi', 'cab', 'edf', 'igh']
group_map = {}

# 遍历数组，按排序后的字符串分组
for s in input_arr:
    # 生成分组键：将字符串字符排序后拼接成新字符串
    key = ''.join(sorted(s))
    # 若键不存在则初始化列表，否则追加当前字符串
    group_map.setdefault(key, []).append(s)

# 将每组列表转换为集合，整理成目标输出格式
output = [set(group) for group in group_map.values()]
print(output)

代码说明 #

1. 遍历输入数组时，对每个字符串的字符排序并拼接，生成唯一的分组键（比如bac排序后得到abc，和原abc共用同一个键）；
2. 使用字典group_map存储分组，键为排序后的字符串，值为对应异位词组成的列表；
3. 最后将字典中的每个列表转换为集合，得到符合要求的输出结构。

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