2-line Python solution, AC with 350ms (some useful Python tricks)


  • 27
    H
        def anagrams(self, strs):
            count = collections.Counter([tuple(sorted(s)) for s in strs])
            return filter(lambda x: count[tuple(sorted(x))]>1, strs)
    
    • collections.Counter creates a counter object. A counter object is like a specific kind of dictionary where it is build for counting (objects that hashes to same value)
    • tuple(sorted(s)) is used here so that anagrams will be hashed to the same value. tuple is used because sorted returns a list which cannot be hashed but tuples can be hashed
    • filter: selects some elements of the list based on given function (first argument - a lambda function is given here)
    • lambda function defined here returns True if number of anagrams of that elements is greater than 1

  • 10
    H

    Here is another python solution which is 4-line but a little more concise and faster (~20ms faster)

        def anagrams(self, strs):
           d = collections.defaultdict(list)
           for s in strs:
               d[tuple(sorted(s))].append(s)  
           return [a for agram_group in d.values() if len(agram_group)>1 for a in agram_group]
    
    • collection.defaultdict is used instead of Counter. It is almost same as dict but you can set default value (the value when item is not found in the dictionary)
    • list comprehension is used in the return statement in order to select anagrams which have more than 1 word and also to flatten the d.values() which is list of lists

  • 0
    B
    This post is deleted!

  • 0
    O

    Awesome, likes to learn something new here ^_^b


  • 0

    Really concise and elegant Python codes :-)


  • 0

    Great list comprehension! I am not good at it and learn something new from your code :-)


  • 10
    R
    def groupAnagrams(self, strs):
        dic = {}
        for item in sorted(strs):
            sortedItem = ''.join(sorted(item))
            dic[sortedItem] = dic.get(sortedItem, []) + [item]
        return dic.values()
    

    Here's my traditional 4-line solution.


  • 0
    I

    @StefanPochmann maybe you could come up with a one line python lol


  • 2

    268ms answer, use dictionary

    class Solution(object):
        def groupAnagrams(self, strs):
            """
            :type strs: List[str]
            :rtype: List[List[str]]
            """
            dictStrs = {}
            for str in strs:
                ls = tuple(sorted(str))
                if not dictStrs.has_key(ls):
                    dictStrs[ls] = []
                dictStrs[ls].append(str)
                            
            resStrs = [] 
            for group in dictStrs.values():
                resStrs.append(group)
            
            return resStrs
    

  • 1
    D

    @yanchao_hust you can return dictStrs.values() directly


  • 0
    L

    @iamkg - does this count?

    Using great ideas from @hebele (tuple(sorted(s))) and defaultdict ... and of course all the great gems from @StefanPochmann all over the forum:

    def groupAnagrams(self, strs):
        return reduce(
                lambda d, x: d[tuple(sorted(x))].append(x) or d,
                strs,
                collections.defaultdict(list)).values()
    

    edit: Just saw @StefanPochmann 's 1-liners @ https://discuss.leetcode.com/topic/21052/1-line-ruby-python-for-updated-problem and learnt itertools.groupby!


  • 1
    A

    here is my 219 ms python solution

    class Solution(object):
        def groupAnagrams(self, strs):
            """
            :type strs: List[str]
            :rtype: List[List[str]]
            """
            list_of_sorted_str = []
            list_of_anagrams = []
            for str in strs:
                list_of_sorted_str.append(''.join(sorted(str)))
            d = {}
            for key,value in enumerate(list_of_sorted_str):
                if value not in d:
                    d[value]=[strs[key]]
                else:
                    d[value].append(strs[key])
            for key in d:
                list_of_anagrams.append(d[key])
            return list_of_anagrams
    

  • 1
    H

    A reduced answer from @ashutoshjha, about beating 93%

    class Solution(object):
        def groupAnagrams(self, strs):
            d = {}
            ans = []
            k = 0
            for str in strs:
                sstr = ''.join(sorted(str))
                if sstr not in d:
                    d[sstr] = k
                    k = k+1
                    ans.append([])
                    ans[-1].append(str)
                else:
                    ans[d[sstr]].append(str)
            return ans
    

  • 0

    @hebele class Solution(object):
    last line we can use this :
    return list(d.values())
    which is more concise.


  • 0
    P

    @yanchao_hust didnt you get time exceeded limit, I did a similar one but I get the error?


  • 0
    G

    @ray24 Hey, why do you use sorted(strs) ? In my opinion, for item in strs will also work ( and maybe it will run faster in this way ?? ), btw intuitive and traditional solution !


  • 0
    C

    @GoldenalCheese Because the standard result is organized in sorted way, for example, ["ate", "eat","tea"], instead of ["eat","tea","ate"]. Anyway, both work. The unsorted version is also accepted.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.