题目
Given an array of strings, group anagrams together.
题意
给定一个字符串数组，将其中颠倒字母而成的字（anagrams），即字母是相同的，但是是不同顺序的字符串放在同一个数组中返回。
例子
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
Note:
- All inputs will be in lowercase.
- The order of your output does not matter.
题解
这里可以先对每个字符进行排序，排好序后就可以判断乱序的单词是否属于同一类单词，将排序后的字符最为key,建立map，value为字符串数组。这里关于排序的解法，由于是26个小写字母，所以可以先将字符映射为整型数组对应的位置，然后再按顺序遍历数组组成字符串，这样就算排序好了，排序的时间复杂度为O(size(word))。
代码
func groupAnagrams(strs []string) [][]string {
resMap := make(map[string][]string)
for _,str := range strs{
na := make([]int,26)
for _,s:=range str{
na[s-'a'] ++
}
strAna := ""
for i,n := range na{
if n!=0{
for num:=0;num<n;num++{
strAna += string(i+'a')
}
}
if len(strAna)== len(str){
break
}
}
if _,ok := resMap[strAna];!ok{
resStr := make([]string,0)
resStr = append(resStr,str)
resMap[strAna] = resStr
}else{
resMap[strAna] = append(resMap[strAna],str)
}
}
res := make([][]string,0)
for _,v := range resMap{
res = append(res,v)
}
return res
}
总结
一开始想象用那种单词树的做法，将单词中每一个节点逐个拿出来然后按照字符对应的边去寻找，最后能匹配的就是放在同一个数组中的。然而并不行，因为是乱序的。
所以最后就是对单词先进行排序，然后再根据排序的结果映射出字符串数组。这里从网上的其他思路得到启发，直接用int数组来进行排序了，毕竟将字母映射为int的下标位置，然后再遍历int数组，组合起来的字符串也是排好序的，所以效率会略高一些。
