Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.1k views
in Technique[技术] by (71.8m points)

string - Anagrams in Python using lists

Imagine we have following list of strings:

Input: ["eat", "tea", "tan", "ate", "nat", "bat"]

The output of our program should group each set of anagram and return them all together as a list as following:

Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

My current solution finds the first set of anagrams but fails to detect the other two and instead, duplicates the first groups into the list:

class Solution(object):
    def groupAnagrams(self, strs):
        allResults=[]
        results=[]
        temp=''
        for s in strs:  
          temp=s[1:]+s[:1]
          for i in range(0,len(strs)):
              if temp==strs[i]:
                results.append(strs[i])
          allResults.append(results)      
        return allResults 

and the output is:

[["ate","eat","tea"],["ate","eat","tea"],["ate","eat","tea"],["ate","eat","tea"],["ate","eat","tea"],["ate","eat","tea"]]

How to fix this issue?

EDIT: I have fixed the duplication in appending by appending the results into allResults outside of second loop:

class Solution(object):
def groupAnagrams(self, strs):
    allResults=[]
    results=[]
    temp=''
    for s in strs:  
      temp=s[1:]+s[:1]
      for i in range(0,len(strs)):
          if temp==strs[i]:
            results.append(strs[i])
    allResults.append(results) 
    print(results)
    return allResults  

Yet, it does not detect the other two sets of anagrams.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

you can do it using defaultdict of python in-built collections library and sorted :

In [1]: l = ["eat", "tea", "tan", "ate", "nat", "bat"]

In [2]: from collections import defaultdict

In [3]: d = defaultdict(list)

In [4]: for x in l:
   ...:     d[str(sorted(x))].append(x)

In [5]: d.values()
Out[5]: dict_values([['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']])

to fix your the solution you need add the variable to check is allready added, for exanmple(and the while walk through the strs i use enumerate for little performance in the search of the anagrams):

class Solution(object):
    def groupAnagrams(self, strs):
        allResults = []
        added = set([])
        temp=''
        for i, s in enumerate(strs):
            results = []
            unique_s = "".join(sorted(s))
            if unique_s in added:
                continue
            else:
                added.add(unique_s)
            for x in strs[i:]:
              if unique_s=="".join(sorted(x)):
                results.append(strs[i])
            allResults.append(results)
print(added)
return allResults

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...