49. Group Anagrams - python3

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

My Answer 1: Accepted (Runtime: 1552 ms - 5.13% / Memory Usage: 18.5 MB - 25.36%)

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        freqList = []
        for i in strs:
            freqCounter = [0]*(26)
            for ch in i:
                freqCounter[ord(ch)-ord('a')] += 1
            freqList.append(freqCounter)
        
        result = []
        
        while freqList:
            freq = freqList.pop()
            tmp = [strs.pop()]
            while freq in freqList:
                idx = freqList.index(freq)
                freqList.pop(idx)
                tmp.append(strs.pop(idx))
            result.append(tmp)
            
        return result

비효율 끝판왕 코드 등장... 런타임 5%..............

우선 freqList 에 각 문자열들의 freqCounter 현황들을 저장하고
ex) eat = [1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
=> a 1개, e 1개, t 1개

하나씩 pop 하면서 같은 값을 갖는 문자열을 찾아 tmp 리스트에 묶어준 후 result 리스트에 저장해 리턴했다

242. Valid Anagram

    int freqCounter[26] = {0};

    // 특정 알파벳이 몇번 등장했는지 count
    while(arr[i] != '\0') {
        freqCounter[arr[i] - 'a']++;
        i++;
    }

전에 풀었던 242 번을 참고해서 접근함

문자 -> 아스키코드 : chr()
아스키코드 -> 문자 : ord()

Approach 2: Categorize by Count

Solution 1: Accepted (Runtime: 108 ms - 36.49% / Memory Usage: 19.9 MB - 7.99%)

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        ans = collections.defaultdict(list)
        for s in strs:
            count = [0] * 26
            for c in s:
                count[ord(c) - ord('a')] += 1
            ans[tuple(count)].append(s)
        return ans.values()

흐름은 같지만 이것의 핵심은 ans[tuple(count)].append(s)
ans 딕셔너리의 크기는 엄청 큰데 그 중에 str 값을 갖는 애들만 출력하는 거 같음 => ans.values()

collections.defaultdict
: key 값이 없을 경우 미리 지정해놓은 초기값을 반환하는 dictionary

Dictionary 에 대한 공부가 필요할 듯