group-anagrams

group-anagrams.py

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        result = []
        groups = {}
        
        for word in strs:
            wordFrecuency = self.__getDictFrecuency(word) # O(n) -> {...}
            groupIndex = self.__belongsToAGroup(groups, wordFrecuency) # O(groups.length + wordFrecuency.length)
            
            if groupIndex > -1:
                result[groupIndex].append(word)
            else:
                groupLen = len(groups)
                groups[groupLen] = wordFrecuency
                result.append([word])
                
        
        return result
    
    def __getDictFrecuency(self, word):
        frecuencies = {}
        
        for c in word:
            frecuencies[c] = frecuencies.get(c, 0) + 1
        
        return frecuencies
    
    def __belongsToAGroup(self, groups, dic) -> int:
        for groupIndex in groups:
            group = groups[groupIndex]
            isEqual = self.__isEqualsAnagram(dic, group) # O(n)
            
            if isEqual:
                return groupIndex
        
        return -1
    
    def __isEqualsAnagram(self, dic, dic2) -> bool:
        if len(dic) != len(dic2):
            return False
        
        for c in dic:
            if c not in dic2 or dic[c] != dic2[c]:
                return False
            
        return True