您现在的位置是:首页 >技术交流 >算法leetcode|49. 字母异位词分组(rust重拳出击)网站首页技术交流

算法leetcode|49. 字母异位词分组(rust重拳出击)

二当家的白帽子 2023-07-02 04:00:02
简介算法leetcode|49. 字母异位词分组(rust重拳出击)


49. 字母异位词分组:

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

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

样例 1:

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

样例 2:

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

样例 3:

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

提示:

  • 1 <= strs.length <= 104
  • 0 <= strs[i].length <= 100
  • strs[i] 仅包含小写字母

分析:

  • 面对这道算法题目,二当家的陷入了沉思。
  • 字母异位词,就是含有相同个数字母,但是排列不同的字符串。
  • 根据字母异位词的定义,可以想到,每个字母异位词的字母,按照相同的排序方法排序后会得到相同的结果,所以第一个方法就是把字符串中的字母排序,然后再按照排序后的词分组即可。
  • 根据字母异位词的定义,还可以想到,只要所含字母的个数都相同,他们就是字母异位词。

题解:

rust:

impl Solution {
    pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
        let mut map = std::collections::HashMap::new();
        strs.into_iter().for_each(|str| {
            let mut counter = [0; 26];
            str.bytes().for_each(|c| counter[(c - b'a') as usize] += 1);
            map.entry(counter).or_insert(vec![]).push(str);
        });
        map.values().cloned().collect()
    }
}

go:

func groupAnagrams(strs []string) [][]string {
    mp := map[[26]int][]string{}
	for _, str := range strs {
		cnt := [26]int{}
		for _, b := range str {
			cnt[b-'a']++
		}
		mp[cnt] = append(mp[cnt], str)
	}
	ans := make([][]string, 0, len(mp))
	for _, v := range mp {
		ans = append(ans, v)
	}
	return ans
}

c++:

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        auto arrayHash = [fn = hash<int>{}](const array<int, 26> &arr) -> size_t {
            return accumulate(arr.begin(), arr.end(), 0u, [&](size_t acc, int num) {
                return (acc << 1) ^ fn(num);
            });
        };

        unordered_map<array<int, 26>, vector<string>, decltype(arrayHash)> mp(0, arrayHash);
        for (string &str: strs) {
            array<int, 26> counts{};
            int length = str.length();
            for (int i = 0; i < length; ++i) {
                ++counts[str[i] - 'a'];
            }
            mp[counts].emplace_back(str);
        }
        vector<vector<string>> ans;
        for (auto it = mp.begin(); it != mp.end(); ++it) {
            ans.emplace_back(it->second);
        }
        return ans;
    }
};

python:

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        mp = collections.defaultdict(list)

        for st in strs:
            counts = [0] * 26
            for ch in st:
                counts[ord(ch) - ord("a")] += 1
            # 需要将 list 转换成 tuple 才能进行哈希
            mp[tuple(counts)].append(st)

        return list(mp.values())


java:

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            int[] counts = new int[26];
            int   length = str.length();
            for (int i = 0; i < length; ++i) {
                ++counts[str.charAt(i) - 'a'];
            }
            // 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串,作为哈希表的键
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 26; ++i) {
                if (counts[i] != 0) {
                    sb.append((char) ('a' + i));
                    sb.append(counts[i]);
                }
            }
            String       key  = sb.toString();
            List<String> list = map.get(key);
            if (list == null) {
                list = new ArrayList<>();
                map.put(key, list);
            }
            list.add(str);
        }
        return new ArrayList<>(map.values());
    }
}

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子:https://le-yi.blog.csdn.net/ 博客原创~


风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。