1 line Ruby/Python for Updated Problem


  • 17

    The problem just got updated, now asking for different results. Here are some solutions for the new version.

    All of them use the sorted string as the group identifier, so for example the words "leetcoder" and "electrode" both have the group identifier "cdeeelort" (or rather an array version of it), which is how I know that they're anagrams of each other.


    Ruby solution 1

    Just sort and group.

    def group_anagrams(strs)
      strs.sort.group_by { |s| s.chars.sort }.values
    end
    

    Ruby solution 2

    Group first, then sort each group. Could be faster for big cases (though isn't for the OJ test cases).

    def group_anagrams(strs)
      strs.group_by { |s| s.chars.sort }.values.map(&:sort)
    end
    

    Python solution 1

    Sort and group by group identifier, then sort each group normally.

    def groupAnagrams(self, strs):
        return [sorted(g) for _, g in itertools.groupby(sorted(strs, key=sorted), sorted)]
    

    Or "breaking it down" to maybe make it more readable for beginners and because I just noticed that in Firefox it violates my self-imposed "no scrollbars" rule (I usually use Chrome and didn't think it differed):

    def groupAnagrams(self, strs):
        groups = itertools.groupby(sorted(strs, key=sorted), sorted)
        return [sorted(members) for _, members in groups]
    

    Python solution 2

    Using defaultdict to collect the groups.

    def groupAnagrams(self, strs):
        groups = collections.defaultdict(list)
        for s in strs:
            groups[tuple(sorted(s))].append(s)
        return map(sorted, groups.values())

  • 1
    C

    not very readable...


  • 1

    I think they are very readable. How familiar are you with Ruby and Python?


  • 1
    Y

    I have use python for more than 3 years. Just think you try to compress too many actions into one line. I guess that's why someone thinks the readability is not good. list comprehension is a cleaver and very pythonic method. But, when people want to study your algorithm idea, it's easier to have step by step code.


  • 4

    I still think they are very readable.

    Grouping is a standard problem and I recently spent an intense month on Python at StackOverflow where grouping came up over and over again and in my experience, the above solutions are the straight-forward standard solutions that get posted and upvoted and accepted all the time. I didn't do the same with Ruby, but I suspect it's the same there. Plus they're even shorter than the Python ones.

    I can see that people unfamiliar with Python/Ruby have trouble reading these, but that's not my fault and it doesn't mean the code is bad. I also don't go to Russia and complain to people that I don't understand them when they speak Russian :-)


  • 2

    Argh, you ninja'd me with your big edit :-) Thanks for answering the "how familiar are you" question after all.

    Yes, a different style might be easier to read for some people. I guess I'm not writing code for these people. I'm just trying to write the best code I can, and readability for beginners isn't a top priority for me. I feel it would be like let's say a novelist only using the simplest English words that everybody knows.


  • 2

    Oh well, I did break that Python one-liner down a bit now. Hope that helps some.


  • 0
    T

    Hi Stefan,
    I think this could be a minor improvement over python solution 2. Sort once instead of map the sort to each smaller list. What do you think?

    for s in sorted(strs):
    
        ...
    
    return groups.values()
    

  • 0

    Well, that's exactly the difference between the two Ruby versions :-)
    I'm not sure what's better. In what way do you think it might be an improvement?

    I think it's a bit clearer to sort each group, because that explicitly does exactly what we're asked to do. If you sort first, you need to think a tiny bit to see that this results in each group being sorted. And if someone had the idea to somehow change something (e.g. collect the strings in sets instead of lists), they'd need to be aware or lucky to not screw up the order.

    About speed, I don't know. Sorting afterwards takes more calls to sorted, but it also shrinks the logarithmic factor. Like if every group has g elements, you have O((n/g) g log(g)) = O(n log g) instead of O(n log n). In the extreme case of all groups having just one element, it's just O(n).


  • 0
    Y

    thanks for the "break down". Personally, i like the two lines version, simply because the line is short (under 80 characters). I don't need to scroll around to see the full line.


  • 0
    L

    Why is sorted(strs, key=sorted) needed?

    I tried the following code :

    import itertools
    strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
    groups = itertools.groupby(strs, sorted)
    print [sorted(members) for _, members in groups]
    

    and the result is this:

    [['eat', 'tea'], ['tan'], ['ate'], ['nat'], ['bat']]
    

    Why can't it working properly?
    Do I have to sort strs before groupby?


  • 0

  • 0

    @yaoaoaoao Yeah, I hate having to scroll the code and not seeing it all at once, but I don't need to scroll to see that long line. Though that's apparently because I usually don't use Firefox. In Chrome I have about three more characters before there would be a scrollbar. Same in Opera and Internet Explorer. Only Firefox creates a scrollbar for me, because it uses a slightly wider font. Argh.

    Anyway, I must admit I like the two-line version as well :-)


  • 0
    X

    @StefanPochmann sir could you please explain why tuple is needed in python 2 that you write?


  • 0

    @xz137 Try it without and you'll see.


  • 0
    Y

    Thanks Stefan. I learn a lot from your code. For python solution 2, I think we don't need to sort the groups. I tried to directly return groups.values() and got accept. Thanks again! Merry Christmas


  • 0
    L

    @StefanPochmann No need to return using map. You could just return group.values()

    def groupAnagrams(self, strs):
            """
            :type strs: List[str]
            :rtype: List[List[str]]
            """
            a=defaultdict(list)
            for s in strs:
                a[tuple(sorted(s))].append(s)
            return a.values()

  • 0
    S

    hi, may i know the complexity of the code?


  • 0
    J

    Hi, so I'm just trying to understand why you'd sort the strings first in your ruby solution, there is no reason to sort the array of strings since it will still need to sort each individual string when using group by. I found the solution without it to be accepted as well

    def group_anagrams(strs)
      strs.group_by { |s| s.chars.sort }.values
    end
    

  • 0

    @jorge-aceves said in 1 line Ruby/Python for Updated Problem:

    why you'd sort the strings first in your ruby solution

    Because the problem requested that "each inner list's elements must follow the lexicographic order".


Log in to reply
 

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