49.Group Anagrams

Tags: [string], [sort], [bucket_sort], [map]

Com: {fb}

Link: https://leetcode.com/problems/anagrams/\#/description

Given an array of strings, group anagrams together.

For example, given:["eat", "tea", "tan", "ate", "nat", "bat"],
Return:

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

Note:All inputs will be in lower-case.

Solution: Map, Bucket Sort

class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        if not strs:
            return []

        str_map = {}
        for i in xrange(len(strs)):
            sorted_c_str = self.sort_c(strs[i])
            if sorted_c_str not in str_map:
                str_map[sorted_c_str] = [i]
            else:
                str_map[sorted_c_str].append(i)

        result = []
        for sorted_c_str in str_map:
            sub = []
            for i in str_map[sorted_c_str]:
                sub.append(strs[i])
            result.append(sub)

        return result

    def sort_c(self, s):
        if not s:
            return s

        c_arr = list(s)
        # bucket sort
        buckets = [[] for _ in xrange(26)]
        for c in c_arr:
            buckets[ord(c) - ord('a')].append(c)

        buff = []
        for bucket in buckets:
            if not bucket:
                continue
            for c in bucket:
                buff.append(c)

        return ''.join(buff)

Revelation:

• Because there only 26 (fix number) lower case English characters, so we can use bucket sort.

Note:

• Time complexity = O(n*k), n is the number of strings, k is the max length of the strings.