49. Group Anagrams

49. Group Anagramsopen in new window

🟠 🔖 数组 哈希表 字符串 排序 🔗 LeetCodeopen in new window

题目

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

Input: strs = [""]
Output: [[""]]

Example 3:

Input: strs = ["a"]
Output: [["a"]]

Constraints:

1 <= strs.length <= 10^4
0 <= strs[i].length <= 100
strs[i] consists of lowercase English letters.

题目大意

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

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

strs[i] 仅包含小写字母

解题思路

异位词这类问题的关键在于，如何迅速判断两个字符串是异位词，主要考察数据编码和哈希表的使用。

可以尝试找到一种编码方法，使得字母异位词的编码相同？找到这种编码方式之后，就可以用一个哈希表存储编码相同的所有异位词，得到最终的答案。

对字符串排序可以是一种编码方案，如果是异位词，排序后就变成一样的了，但是这样时间复杂度略高，且会修改原始数据。

更好的编码方案是利用每个字符的出现次数进行编码，也就是下面的解法代码。

代码

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {
	let res = {};
	for (let str of strs) {
		let encodeStr = encode(str);
		if (!res[encodeStr]) {
			res[encodeStr] = [];
		}
		res[encodeStr].push(str);
	}
	return Object.values(res);
};

var encode = function (str) {
	let res = new Array(26).fill(0);
	for (let i of str) {
		let code = i.charCodeAt() - 'a'.charCodeAt();
		res[code]++;
	}
	return res.join('_');
};

49. Group Anagrams

# 49. Group Anagramsopen in new window

# 题目

# 题目大意

# 解题思路

# 代码

# 相关题目

49. Group Anagramsopen in new window

题目

题目大意

解题思路

代码

相关题目