Python算法题集_字母异位词分组-Toy模板网

这篇具有很好参考价值的文章主要介绍了Python算法题集_字母异位词分组。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

本文为Python算法题集之一的代码示例

题目49：字母异位词分组

说明：给你一个字符串数组，请你将 字母异位词 组合在一起，可以按任意顺序返回结果列表

字母异位词 ：是由重新排列原单词所有字母得到的新单词

使用同步数组list和检索集合set

def groupAnagrams_ext1(self, strs):
    iLen = len(strs)
    setlist = []
    for iIdx in range(iLen):
        setlist.append(sorted(strs[iIdx]))
    allset = []
    for aSet in setlist:
        if aSet in allset:
            continue
        allset.append(aSet)
    result=[]
    for aSetItem in allset:
        tmpResultItem=[]
        for iIdx in range(iLen):
            if setlist[iIdx] == aSetItem:
                tmpResultItem.append(strs[iIdx])
        result.append(tmpResultItem)
    return result

astr = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(groupAnagrams_ext1(astr))
# 运行结果
# [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

使用同步数组list和结果数组list

def groupAnagrams_ext2(self, strs):
    iLen = len(strs)
    sortlist = []
    for iIdx in range(iLen):
        sortlist.append(sorted(strs[iIdx]))
    result, resultsort=[], []
    for iIdx in range(iLen):
        if sortlist[iIdx] in resultsort:
            result[resultsort.index(sortlist[iIdx])].append(strs[iIdx])
        else:
            resultsort.append(sortlist[iIdx])
            result.append([strs[iIdx]])
    return result

astr = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(groupAnagrams_ext2(astr))
# 运行结果
# [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

使用字典和元组

def groupAnagrams_ext3(self, strs):
    from collections import Counter
    anagrams = {}
    for s in strs:
        counter = Counter(s)
        key = tuple(sorted(counter.items()))
        if key not in anagrams:
            anagrams[key] = []
        anagrams[key].append(s)
    return list(anagrams.values())

    
astr = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(groupAnagrams_ext3(astr))
# 运行结果
# [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]