0049.字母异位词分组

方法一：暴力搜索

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。

func groupAnagrams(strs []string) [][]string {
	ans, used, n := [][]string{}, make([]bool, len(strs)), len(strs)
	for i := 0; i < n; i++ {
		if used[i] {
			continue
		}
		tmp := []string{strs[i]}
		used[i] = true
		for j := i + 1; j < n; j++ {
			if isAnagrams(strs[j], strs[i]) {
				tmp, used[j] = append(tmp, strs[j]), true
			}
		}
		ans = append(ans, tmp)
	}
	return ans
}

func isAnagrams(now, target string) bool {
	if len(now) != len(target) {
		return false
	}
	nc, tc := [26]int{}, [26]int{}
	for i := 0; i < len(now); i++ {
		nc[int(now[i]-'a')] += 1
		tc[int(target[i]-'a')] += 1
	}
	for i := 0; i < 26; i++ {
		if nc[i] != tc[i] {
			return false
		}
	}
	return true
}
impl Solution {
    pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
        fn is_anagrams(a: &str, b: &str) -> bool {
            if a.len() != b.len() {
                return false;
            }
            let a = a.as_bytes();
            let b = b.as_bytes();
            let (mut ac, mut bc) = (vec![0; 26], vec![0; 26]);
            for i in 0..a.len() {
                let ac_idx = (a[i] - ('a' as u8)) as usize;
                ac[ac_idx] += 1;
                let bc_idx = (b[i] - ('a' as u8)) as usize;
                bc[bc_idx] += 1;
            }
            for i in 0..26 {
                if ac[i] != bc[i] {
                    return false;
                }
            }
            true
        }

        let (mut ans, mut used, n) = (vec![], vec![false; strs.len()], strs.len());
        for i in 0..n {
            if used[i] {
                continue;
            }
            used[i] = true;
            let mut tmp = vec![strs[i].clone()];
            for j in i + 1..n {
                if is_anagrams(&strs[i], &strs[j]) {
                    tmp.push(strs[j].clone());
                    used[j] = true;
                }
            }
            ans.push(tmp);
        }
        ans
    }
}

方法二：排序 + 哈希

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

func groupAnagrams(strs []string) [][]string {
	ans, help := [][]string{}, make(map[string][]string)
	for _, str := range strs {
		s := []byte(str)
		sort.Slice(s, func(i, j int) bool { return s[i] < s[j] })
		help[string(s)] = append(help[string(s)], str)
	}
	for _, v := range help {
		ans = append(ans, v)
	}
	return ans
}
impl Solution {
    pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
        use std::collections::HashMap;
        let mut map: HashMap<Vec<u8>, Vec<String>> = HashMap::new();
        for s in strs {
            let mut v = s.as_bytes().to_vec();
            v.sort();
            map.entry(v).or_insert(Vec::new()).push(s);
        }
        map.into_iter().map(|(_, v)| v).collect()
    }
}