[LeetCode] 49. Group Anagrams

https://leetcode.com/problems/group-anagrams/description/

LeetCode - The World's Leading Online Programming Learning Platform

LeetCode - Group Anagrams

문제 유형 : 문자열 처리, 해시

문제 난이도 : Medium

 

문제

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.

 

문자열 배열 strs가 주어진다.

애너그램 문자열끼리 묶으시오. 어느 순서로든 상관없습니다.

애너그램은 글자를 재배열하여 만들 수 있는 문자열을 말합니다.

 

풀이

해시맵을 만들어서 (정렬된 문자열)-(인덱스)로 자료를 저장한다.

애너그램이라면, 두 문자열을 정렬했을 때 똑같으므로 바로 삽입할 위치를 찾을 수 있다.

 

순차적으로 문자열을 탐색하면서 매번 정렬된 문자열을 만든다.

그리고 해시 맵에서 찾은 뒤, 값이 없으면 맨 뒤에 붙이고, 해시맵의 값에 인덱스를 붙여주면 된다.

값이 있다면 해시 맵에서 인덱스를 꺼내서 그 부분에 넣으면 된다.

 

코드

C++

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ans;
        unordered_map<string, int> mp;
        int i = 1;

        for(const auto &str : strs) {
            string s = str;
            sort(s.begin(), s.end());

            if(!mp[s]) {
                mp[s] = i++;
                ans.push_back({str});
            } else {
                ans[mp[s]-1].push_back(str);
            }
        }

        return ans;
    }
};

 

Go

func groupAnagrams(strs []string) [][]string {
    ans := [][]string{}
    mp := make(map[string]int)
    i := 1

    for _, str := range strs {
        s := sortString(str)

        if _, ok := mp[s]; !ok {
			mp[s] = i
			i++
			ans = append(ans, []string{str})
		} else {
			ans[mp[s]-1] = append(ans[mp[s]-1], str)
		}
    }

    return ans;
}

func sortString(s string) string {
	r := []rune(s)
	sort.Sort(sortRunes(r))
	return string(r)
}

type sortRunes []rune

func (s sortRunes) Len() int           { return len(s) }
func (s sortRunes) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
func (s sortRunes) Less(i, j int) bool { return s[i] < s[j] }