package main

import (
	"sort"
)

// RuneSlice implements sort.Interface
type RuneSlice []rune

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

func groupAnagrams(strs []string) (res [][]string) {
	// sorted str : index
	m := map[string]int{}
	for _, v := range strs {
		runes := []rune(v)
		sort.Sort(RuneSlice(runes))
		if idx, ok := m[string(runes)]; !ok {
			m[string(runes)] = len(m)
			res = append(res, []string{v})
		} else {
			res[idx] = append(res[idx], v)
		}
	}
	return res
}

/* func main() {
	a1 := []string{"eat", "tea", "tan", "ate", "nat", "bat"}
	fmt.Println(groupAnagrams(a1))
	a2 := []string{}
	fmt.Println(groupAnagrams(a2))
} */