Rust每日一题(9)---数据结构-字典--group-anagrams

leetcode地址 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

示例 1：

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2：

输入: strs = [""]
输出: [[""]]

示例 3：

输入: strs = ["a"]
输出: [["a"]]

难度: 中等

知识点

• HashMap Entry 相关API

思路

核心还是分析关键操作步骤，主要思路是将strs数组中每个出现的元素做成与字符顺序无关的key，然后遇到相同的key就把改数据push到key对应的value里。key主要有两种实现方式:

1. 将strs中的每个元素转换成bytes然后排序作为key，算法复杂度近似于O(N*log(N))。

use std::collections::HashMap;

impl Solution {
    pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
        let mut map = HashMap::new();

        for _str in strs {
            let mut key = Vec::from(_str.as_bytes()) ;
            key.sort();
            let key:String = String::from_utf8(key).unwrap();
            let vals = map.entry(key).or_insert(vec![]);
            vals.push(_str);
        }
        map.into_values().collect()
    }
}

2. 考虑更简单的key生成方式，比如先对strs中的每个元素转换为字符数组，然后对其分别做乘法和加法运算，经试验未出现hash碰撞，算法复杂度O(2*N)。

   
   use std::collections::HashMap;

impl Solution { pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> { let mut map = HashMap::new(); for _str in strs { let mut key:u64 = 1; for &val in _str.as_bytes() { key *= val as u64; } for &val in _str.as_bytes() { key += val as u64; } let vals = map.entry(key).or_insert(vec![]); vals.push(_str); } map.into_values().collect() } }