Group Anagrams Python Solution with Explainations


  • 0
    W
    class Solution(object):
        def createDict(self, str):
            dict = {}
            for s in str:
                if s in dict:
                    dict[s] += 1
                else:
                    dict[s] = 1
            return dict
        
        def groupAnagrams(self, strs):
            """
            :type strs: List[str]
            :rtype: List[List[str]]
            """
            anagramDict = {}
            for str in strs:
                dict = sorted(self.createDict(str).items())
                dictNew = ",".join([x[0] for x in dict]) + ",".join("%s" %x[1] for x in dict)
                if dictNew not in anagramDict:
                    anagramDict[dictNew] = []
                anagramDict[dictNew].append(str)
            
            return anagramDict.values()
    
    1. Test cases:
      [""]
      ["eat", "tea", "tan", "ate", "nat", "bat"]
      ["", "eat", "tea", "tan", "ate", "nat", "bat", ""]
      ["ems","mes"]
      Expected answers:
      [[""]]
      [["tan","nat"],["eat","tea","ate"],["bat"]]
      [["",""],["tan","nat"],["eat","tea","ate"],["bat"]]
      [["ems","mes"]]

    2. string manipulation in Python:
      (1) e.g. myList = [1, 2, 3, 4, "tro", "lo", "lo", [7, 8, 9], {"i_am": "dictionary"}]
      ["%s" %x for x in myList] or:
      [str(x) for x in myList] or:
      map(str, myList)
      (2) ",".join("") will return "", thus the [""] case would be included in the
      above solution code.

    3. Python dictionary does not accept non primitive type as keys, i.e. only string, integer, doubles
      can be keys, but not list, dictionary, etc. That is why we need to convert dict to
      strings.

    4. Remember to sort the dictionary before converting it to string. Or else it would
      return different result for anagrams e.g. "ems" and "mes": "mse111" and "esm111".
      Method to sort dictinaries:
      sorted(dict.items()) # [("a", 1), ("b", 1), ("c", 1)]


Log in to reply
 

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