{"content":{"title":"Rust每日一题(9)---数据结构-字典--group-anagrams","body":"# Rust每日一题(9)---数据结构-字典--group-anagrams\r\n[leetcode地址](https:\/\/leetcode.cn\/problems\/-group-anagrams\/)\r\n给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。\r\n\r\n字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。\r\n\r\n**示例 1：**\r\n```\r\n输入: strs = [\"eat\", \"tea\", \"tan\", \"ate\", \"nat\", \"bat\"]\r\n输出: [[\"bat\"],[\"nat\",\"tan\"],[\"ate\",\"eat\",\"tea\"]]\r\n```\r\n**示例 2：**\r\n```\r\n输入: strs = [\"\"]\r\n输出: [[\"\"]]\r\n```\r\n\r\n**示例 3：**\r\n```\r\n输入: strs = [\"a\"]\r\n输出: [[\"a\"]]\r\n```\r\n\r\n**难度: 中等**\r\n\r\n## 知识点\r\n- HashMap[ Entry 相关API](https:\/\/doc.rust-lang.org\/std\/collections\/hash_map\/struct.HashMap.html#method.entry)\r\n\r\n## 思路\r\n核心还是分析关键操作步骤，主要思路是将strs数组中每个出现的元素做成与字符顺序无关的key，然后遇到相同的key就把改数据push到key对应的value里。key主要有两种实现方式:\r\n\r\n1. 将strs中的每个元素转换成bytes然后排序作为key，算法复杂度近似于O(N*log(N))。\r\n\r\n```\r\nuse std::collections::HashMap;\r\n\r\nimpl Solution {\r\n    pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {\r\n        let mut map = HashMap::new();\r\n        \r\n        for _str in strs {\r\n            let mut key = Vec::from(_str.as_bytes()) ;\r\n            key.sort();\r\n            let key:String = String::from_utf8(key).unwrap();\r\n            let vals = map.entry(key).or_insert(vec![]);\r\n            vals.push(_str);\r\n        }\r\n        map.into_values().collect()\r\n    }\r\n}\r\n```\r\n\r\n2. 考虑更简单的key生成方式，比如先对strs中的每个元素转换为字符数组，然后对其分别做乘法和加法运算，经试验未出现hash碰撞，算法复杂度O(2*N)。\r\n```\r\nuse std::collections::HashMap;\r\n\r\nimpl Solution {\r\n    pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {\r\n        let mut map = HashMap::new();\r\n        for _str in strs {\r\n            let mut key:u64 = 1;\r\n            for &val in _str.as_bytes() {\r\n                key *= val as u64;\r\n            }\r\n            for &val in _str.as_bytes() {\r\n                key += val as u64;\r\n            }\r\n            let vals = map.entry(key).or_insert(vec![]);\r\n            vals.push(_str);\r\n        }\r\n        map.into_values().collect()\r\n    }\r\n}\r\n```"},"author":{"user":"https:\/\/learnblockchain.cn\/people\/720","address":null},"history":null,"timestamp":1662080063,"version":1}