Python solution using 26-string to represent an anagram


  • 0

    I used a string of length 26 to represent the anagram. The running time should be O(n*k) (plus the final sorting time), with n being the number of words and k being the average length of all words. The running time in OJ is slow, not sure which part could be faster.

    def get_anagram_string(word):
        '''calculate the 26 string-key'''
        string = [0]*26
        for i in word:
            string[ord(i) - ord('a')] += 1
        
        return ''.join([str(i) for i in string])
      
    
    class Solution(object):
        def groupAnagrams(self, strs):
            """
            :type strs: List[str]
            :rtype: List[List[str]]
            """
            
            res = {}
            
            for word in strs:
                anagram_string = get_anagram_string(word)
                if anagram_string in res:
                    res[anagram_string].append(word)
                else:
                    res[anagram_string] = [word]
            
            for k in res:
                res[k] = sorted(res[k])
                
            return res.values()

Log in to reply
 

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