49. 字母异位词分组

每天一道Rust-LeetCode(2019-11-20)

坚持每天一道题,刷题学习Rust.

题目描述

给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。

示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
说明:

所有输入均为小写字母。
不考虑答案输出的顺序。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/group-anagrams
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

思路:
这个实际上是将字符串分组,新来一个字符串,看看他和哪个类似,然后放到一组中.

  1. 盼到两个字符串是否类似,一种是排序后看是否一致,另一种是统计字符出现的个数
  2. 第一种是把排序后的字符串作为map的key,第二种则是把结构体作为map的key
    第二种的结构体可以设计为count[26],其中count[0]表示字符a的个数,count[25]表示字符z的个数
    相比之下,第一种可能会更好一点
    排序是O(KLogK),查找用HashMap是O(1),总体时间复杂度是O(N*KLogK)
    其中N是字符串的个数,K则是某个字符串的长度, 这里没有考虑的是字符串Hash的复杂度,如果一个字符串长度为1万呢?
    至少要遍历一遍,因此复杂度是O(K)

    解题过程

use std::collections::HashMap;

struct Solution;

impl Solution {
    pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
        let mut m = HashMap::new();
        for s in strs {
            let mut s2: Vec<_> = s.clone().into_bytes();
            s2.sort();
            //            println!("s={}", s);
            m.entry(s2).or_insert(Vec::new()).push(s);
        }
        //        println!("m={:?}", m);
        let mut v = Vec::new();
        //这里能否避免复制字符串呢?
        for t in m.iter() {
            v.push(t.1.clone());
        }
        v
    }
}
#[cfg(test)]
mod tests {
    use super::*;
    use crate::share::*;

    #[test]
    fn test() {
        let t = Solution::group_anagrams(
            vec!["eat", "tea", "tan", "nat", "bat", "tan"]
                .iter()
                .map(|n| String::from(*n))
                .collect(),
        );
        println!("t={:?}", t);
    }
}

一点感悟

其他

欢迎关注我的github,本项目文章所有代码都可以找到.