字母异位词分组

1. 题目描述

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

2. 思路

• 暴力法
• hash

3. 实现

3.1. 暴力法

package main

import "sort"

func groupAnagrams(strs []string) [][]string {
	if len(strs) == 0 {
		return nil
	}

	res := make([][]string, 0)

	visited := make(map[string]bool, 0)
	for i := 0; i < len(strs); i++ {
		runes := []rune(strs[i])
		sort.Slice(runes, func(i, j int) bool {
			if runes[i] < runes[j] {
				return true
			} else {
				return false
			}
		})
		if visited[string(runes)] {
			continue
		}
		group := make([]string, 0)
		group = append(group, strs[i])
		for j := i + 1; j < len(strs); j++ {
			runes2 := []rune(strs[j])
			sort.Slice(runes2, func(i, j int) bool {
				if runes2[i] < runes2[j] {
					return true
				} else {
					return false
				}
			})
			if string(runes2) == string(runes) {
				group = append(group, strs[j])
			}
		}

		res = append(res, group)

		visited[string(runes)] = true

	}
	return res
}

3.2. hash

func groupAnagrams2(strs []string) [][]string {
	if len(strs) == 0 {
		return nil
	}

	res := make([][]string, 0)

	groups := make(map[string][]string, 0)
	for i := 0; i < len(strs); i++ {
		runes := []rune(strs[i])
		sort.Slice(runes, func(i, j int) bool {
			if runes[i] < runes[j] {
				return true
			} else {
				return false
			}
		})
		str := string(runes)
		list, ok := groups[str]
		if ok {
			groups[str] = append(list, strs[i])
		} else {
			groups[str] = []string{strs[i]}

		}
	}

	for _, group := range groups {
		res = append(res, group)
	}

	return res
}

4. 参考

• 49. 字母异位词分组 - 力扣（LeetCode）