Group Anagrams - LeetCode

문제 풀이 아이디어

하나의 단어에 쓰인 알파벳의 순서를 바꾸었을 때 다른 단어를 만들 수 있다면 두 단어는 아나그램의 관계라고 정의할 수 있다. 따라서 동일한 알파벳 구성을 가진 두 단어를 의미한다.

따라서 아나그램을 찾기 위해서는 하나하나 비교하는 방법도 있겠으나 완전탐색은 속도적으로 느리다. 따라서 여기서는 하나의 단어에 쓰인 알파벳을 정렬한 것을 비교해서 두 단어가 아나그램 관계인지 확인하는 방법을 사용했다.

예를 들어 eat과 ate은 아나그램의 관계인데 쓰인 알파벳을 정렬하면 “aet”로 동일하다. 따라서 정렬한 알파벳이 동일하다면 두 단어는 아나그램 관계라고 볼 수 있다.

코드

나머지 설명은 코드에 적었다. Dictionary(grouping:, by:)을 사용하면 쉽게 정렬한 알파벳이 동일한 단어끼리 묶을 수 있다.

class Solution {
    func groupAnagrams(_ strs: [String]) -> [[String]] {
        let anagrams = strs.map { ($0, String($0.sorted())) }
        // 👉 (원래 단어, 정렬한 알파벳)의 튜플 형태로 변형한다.
        let dict = Dictionary(grouping: anagrams, by: { $0.1 })
        // 👉 gruop 사용해서 정렬된 알파벳이 동일한 원소끼리 grouping을 한다.
        return dict.values.map { $0.map { $0.0 } }
        // 👉 dict의 value만을 취하고 [(원래 단어, 정렬한 알파벳)]에서 이제 원래 단어만 취해서 리턴한다.
    }
}