Anagram grouping

 Anagram

Anagram은 일반적으로 모든 원본 문자를 정확히 한 번 사용하여

다른 단어 나 구의 문자를 재배열하여 형성 된 단어 또는 문구이다.

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

Input: strs = [""]
Output: [[""]]

Example 3:

Input: strs = ["a"]
Output: [["a"]]
 

Constraints:
1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] consists of lower-case English letters.

 

키포인트

애너그램의 문제의 핵심은 정렬하여 비교하는 것인데, 

두 문자열이 애너그램이라면 sorted 함수의 인자로 줬을 때 결국 같은 값이 나오게 된다. (핵심)

def are_anagrams(a, b):
    return sorted(a) == sorted(b)

print(are_anagrams('listen', 'silent'))
print(are_anagrams('pop', 'odd'))

True
False

 

또한, 목적은 같은 애너그램끼리 묶는다는 것을 인지하고 풀도록하자.

도중에 딴길로 세서 뻘짓을 많이하였다.

 

먼저, strs에서 하나의 요소를 가져와 그 요소를 정렬한다.

정렬 한 요소를 키 값을 기준으로 동일한 인수(여기선 동일한 문자열)을 리스트로 묶어 딕셔너리에 추가해준다.

({"A" : ['abc', 'bac', 'cab'], "B" : ['qw', 'wq']} 형식이다)

후에 값에 해당하는 값만을 리턴해주면 된다.

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        my_dict = {}
        
        for char in strs:
            key = ''.join(sorted(char))
            if key not in my_dict:
                my_dict[key] = [char]
            else:
                my_dict[key] += [char]
        
        return my_dict.values()

# [["eat","tea","ate"],["tan","nat"],["bat"]]


print(my_dict)
# {'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat'], 'abt': ['bat']}

 

---

시간복잡도

for문 O(n)

정렬! O(n log n)

전형적인 쓸만한 정렬 알고리즘의 속도를 확인 할 수 있었다.