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

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

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"]]

难度: 中等

知识点

思路

核心还是分析关键操作步骤,主要思路是将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()
    }
}
  1. 考虑更简单的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() } }

本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

  • 发表于 2022-09-02 08:54
  • 阅读 ( 260 )
  • 学分 ( 1 )
  • 分类:Rust

0 条评论

请先 登录 后评论
Johnathan
Johnathan

PhD

24 篇文章, 1335 学分