前言
新的一年，好好学习
正文
问题来源
本问题来自leetcode上的49题。
问题描述
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例 1:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
分析：
主体思想：暴力 时间复杂度：O(N^3) 字符串比较时间复杂度也需要算入 详细过程：首先判断是否字典内存在相同已排序的字符串，如果存在就在最终结果相同索引位置加入元素；如果不存在就将已排序的字符串加入字典，同时开辟空间将字符串加入，并将开辟好的空间加入最终结果内。
//go语言没有将字符串内元素排序的函数
type sortRunes []rune
func (s sortRunes) Less(i, j int) bool {
return s[i] < s[j]
}
func (s sortRunes) Swap(i, j int) {
s[i], s[j] = s[j], s[i]
}
func (s sortRunes) Len() int {
return len(s)
}
//调用接口
func SortString(s string) string {
r := []rune(s)
//调用go自带函数
sort.Sort(sortRunes(r))
return string(r)
}
func groupAnagrams(strs []string) [][]string {
ret := make([][]string, 0)
m := make([]string, 0)
for i := 0; i < len(strs); i++ {
temp := SortString(strs[i]) //排序字符串
flag := false
for j := 0; j < len(m); j++ {
if temp == m[j] {
flag = true//已找到
ret[j] = append(ret[j], strs[i])//在最终结果相同索引处加入该字符串
}
}
if false == flag { //并未找到排序的相同字符串
m = append(m, temp) //加入字典
retTemp := append([]string{}, strs[i]) //开辟空间并加入
ret = append(ret, retTemp)//加入最终结果
}
}
return ret
}
提交结果：
执行用时: 956 ms, 在Group Anagrams的Go提交中击败了7.75% 的用户
内存消耗: 122.9 MB, 在Group Anagrams的Go提交中击败了36.36% 的用户
并不是很满意这样的一个提交结果。
可以将排序的字符串放入map而不是slice。若是输入的字符串过长（远超26个字符），可以将SortString改为如下函数。排序的时间复杂度为n * logn。
func countSort(s string) string {
var cnt [26]int
for i := 0; i < len(s); i++ {
cnt[s[i]-byte('a')]++
}
ret := make([]byte, len(s))
j := 0
for i := 0; i < 26; i++ {
for k := 0; k < cnt[i]; k++ {
ret[j] = byte(i) + byte('a')
j++
}
}
return string(ret)
}
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
}
总结：
勤思考。
结语
不管怎么样好好加油。
