49. Group Anagrams

Group Anagrams - LeetCode

1. 소팅된 문자열을 Key로 하는 Dict(HashMap)을 이용한 풀이

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        dict1={}
        for str in strs:
            temp="".join(sorted(list(str)))
            if temp not in dict1:
                dict1[temp]=[str]
            else:
                dict1[temp].append(str)
        return dict1.values()
        

문자열을 소팅하고, 소팅한 문자열을 Key로 하는 Dict을 만들어서 해결했다. 하지만 모든 문자열을 정렬하고 처리해야 하기 때문에 약간 빡빡하게 제한시간이 걸린다면 TLE가 날 수도 있다.

 

2. 문자열을 소팅 없이 Counting 한 결과를 Key로 하는 Dict(HashMap)을 이용한 풀이

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        dict1={}
        
        def count(input_string):
            count_list=[0]*26
            for char in input_string:
                count_list[ord(char)-ord("a")]+=1
            # python dict의 key값에는 모든 것이 가능하다
            # tuple도 가능하기 때문에 key로 사용할 수 있음
            return tuple(count_list)
            
        
        for str in strs:
            temp=count(str)
            if temp not in dict1:
                dict1[temp]=[str]
            else:
                dict1[temp].append(str)
        return dict1.values()
        

입력된 문자열을 선형 탐색해서 알파벳 빈도수를 key로 하는 Dict을 사용해 풀 수 있다.

예시

abce -> 111010000000000000... 0

abd -> 11010000000000000... 0

 

그리고 위 결과를 굳이 문자열로 바꿀 필요도 없이 tuple 상태에서 바로 사용해도 Python에서는 잘 동작한다.