/*
 * @lc app=leetcode.cn id=49 lang=golang
 *
 * [49] 字母异位词分组
 */

// 3. hash
// @lc code=start
func groupAnagrams(strs []string) [][]string {
	mp := map[[26]int][]string{}
	for _, str := range strs {
		cnt := [26]int{}
		for _, b := range str {
			cnt[b-'a']++
		}
		mp[cnt] = append(mp[cnt], str)
	}
	ans := make([][]string, 0, len(mp))
	for _, v := range mp {
		ans = append(ans, v)
	}
	return ans
}

// @lc code=end

// 2. hash
// @lc code=start
func groupAnagrams(strs []string) [][]string {
	mp := map[string][]string{}
	for _, str := range strs {
		s := []byte(str)
		sort.Slice(s, func(i, j int) bool { return s[i] < s[j] })
		sortedStr := string(s)
		mp[sortedStr] = append(mp[sortedStr], str)
	}
	ans := make([][]string, 0, len(mp))
	for _, v := range mp {
		ans = append(ans, v)
	}
	return ans
}

// @lc code=end

// 1. 暴力超时
// @lc code=start
func groupAnagrams(strs []string) (ans [][]string) {
	for i := 0; i < len(strs); i++ {
		temp := []string{strs[i]}
		for j := i + 1; j < len(strs); j++ {
			if isAnagram(strs[i], strs[j]) {
				temp = append(temp, strs[j])
				strs = append(strs[:j], strs[j+1:]...)
				j--
			}
		}
		ans = append(ans, temp)
	}
	return
}

func isAnagram(s string, t string) bool {
	s1, s2 := []byte(s), []byte(t)
	sort.Slice(s1, func(i, j int) bool { return s1[i] < s1[j] })
	sort.Slice(s2, func(i, j int) bool { return s2[i] < s2[j] })
	return string(s1) == string(s2)
}

// @lc code=end