Anagram Groups

문제

해답참조

Leet Code Answers

1. Hash Table

• Time complexity: O(m∗n)
  Space complexity: O(m)

#해답참조
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        res = defaultdict(list)

        for s in strs:
        # 선언 count= [0], [0], [0], [0] ... [0] 
        # a~z까지의 방을 만들어줌...
            count = [0] * 26 #a...z
            
            # 그러고 s는 List[str]에 있는 문자열이니까 그 문자열 문자 하나하나를 루프돌림.
            # 해당 문자가 등장할 때마다, 해당 인덱스의 값을 1씩 증가시킴
            for c in s :
                count[ord(c) - ord("a")] += 1
                
            # count = [1, 0, 0, 0, 1, 0, 0, ..., 1, 0, 0]  == 'a': 1, 'e': 1, 't': 1
            # res = { (1, 0, 0, 0, 1, 0, ..., 1): ["eat", "tea"] }
            res[tuple(count)].append(s)


        return res.values()
           

• res[tuple(count)].append(s) : 튜플로 반환하는 이유는 리스트를 딕셔너리의 키로 사용할 수 없기 때문입니다. --> 튜플을 키로 씀
• Q. res는 딕셔너리 인데, 어떻게 밸류값이 리스트가 될수있나?
  A. defaultdict(list)를 사용하기 때문입니다. 이를 통해 자동으로 값(밸류)이 리스트로 초기화됩니다. (만약 defaultdict(int)면 정수 값을 기본값으로 가지는 딕셔너리입니다.만약 존재하지 않는 키에 접근하면 자동으로 값이 0으로 설정됩니다.)

2. sorting

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        res = defaultdict(list)
        for s in strs:
            sortedS = ''.join(sorted(s))
            res[sortedS].append(s)
        return res.values()

• ''.join(sorted_s): 리스트를 하나의 문자열로 합치는 메서드
  • ''.join() 메서드는 리스트나 튜플처럼 반복 가능한 객체의 요소들을 하나의 문자열로 합치는 역할을 합니다.
  • ''은 빈 문자열을 의미하며, 리스트의 요소들을 빈 문자열로 연결한다는 뜻입니다.
  • 따라서 ''.join(sorted_s)는 리스트의 각 문자를 합쳐 하나의 문자열을 만듭니다.
  • sorted(s)로 문자열을 알파벳 순으로 정렬한 후, ''.join()을 사용해 정렬된 문자들을 하나의 문자열로 다시 합칩니다.
• res[sortedS] = res["aet"], res["ant"] ...이런거
  --> 꼭 숫자가 아니어도됨.