当前位置：首页 > news >正文

LeetCode字母异位词分组

news 来源：原创 2024/9/20 21:35:59

题目描述

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

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

示例 1:

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

示例 2:

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

示例 3:

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

解题思路

对于输入数组中的每个字符串，通过排序字符来创建一个唯一的键，然后根据这个键将变位词分组。最后，将所有分组的结果收集到一个数组中并返回。这种方法不依赖于外部库，只使用了JavaScript的内置Map对象。

代码

/*** @param {string[]} strs* @return {string[][]}*/
var groupAnagrams = function(strs) {var res = [];var map = new Map();for(var i=0;i<strs.length;i++){var k = strs[i].split('').sort().join('');if(map.has(k)){map.get(k).push(strs[i]);}else{map.set(k, [strs[i]]);    }}map.forEach((val, key)=>{res.push(val);})return res;};

代码分析

这段代码用于将一个字符串数组strs中的变位词分组。下面是逐行分析：

var groupAnagrams = function(strs) {
- 定义了一个名为groupAnagrams的函数，它接受一个参数strs，这是一个字符串数组。
var res = [];
- 定义了一个空数组res，用于存储最终的分组结果。
var map = new Map();
- 创建了一个新的Map对象，用于存储中间的分组结果。Map对象是一种键值对集合，可以记住键的原始插入顺序。
for(var i=0;i<strs.length;i++){
- 开始一个循环，遍历输入数组strs中的每个字符串。
var k = strs[i].split('').sort().join('');
- 对于当前循环中的字符串strs[i]，将其拆分成字符数组，对数组进行排序，然后将排序后的数组重新连接成一个字符串。这个字符串k将作为分组的键。
if(map.has(k)){
- 检查Map对象中是否已经存在键k。
map.get(k).push(strs[i]);
- 如果键k已经存在，那么将当前字符串strs[i]添加到与键k相关联的数组中。
}else{
- 如果键k不存在，执行下面的代码。
map.set(k, [strs[i]]);
- 将键k和一个新的数组（包含当前字符串strs[i]）作为键值对添加到Map对象中。
}
- 结束if语句。
}
- 结束for循环。
map.forEach((val, key)=>{
- 使用Map对象的forEach方法遍历所有键值对。
res.push(val);
- 对于每个键值对，将值（即分组后的字符串数组）添加到结果数组res中。
})
- 结束forEach方法的回调函数。
return res;
- 函数返回结果数组res，它包含了所有分组后的变位词数组。
};
- 结束函数定义。

案例：

使用字符串数组strs = ["eat", "tea", "tan", "ate", "nat", "bat"]来演示groupAnagrams函数如何工作。下面是具体的步骤和结果：

初始化：
- res 初始化为空数组。
- map 初始化为一个新的空Map对象。
遍历字符串数组：
- 对于每个字符串，我们通过strs[i].split('').sort().join('')生成一个排序后的字符串作为键。
分组：
- 根据生成的键，我们将字符串分组到map中。
收集结果：
- 遍历map，将每个分组的字符串数组添加到结果数组res中。
返回结果。

手动模拟这个过程：

对于字符串 "eat"，排序后的键是 "aet"。
- map 现在包含 {"aet": ["eat"]}
对于字符串 "tea"，排序后的键也是 "aet"。
- map 更新为 {"aet": ["eat", "tea"]}
对于字符串 "tan"，排序后的键是 "ant"。
- map 现在包含 {"aet": ["eat", "tea"], "ant": ["tan"]}
对于字符串 "ate"，排序后的键同样是 "aet"。
- map 更新为 {"aet": ["eat", "tea", "ate"], "ant": ["tan"]}
对于字符串 "nat"，排序后的键是 "ant"。
- map 更新为 {"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"]}
对于字符串 "bat"，排序后的键是 "abt"。
- map 现在包含 {"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"], "abt": ["bat"]}

最终结果：
- 遍历map，将值（即分组的数组）添加到res中，得到最终结果。

最终的res数组将是：

[["eat", "tea", "ate"],["tan", "nat"],["bat"]
]

这个结果表示 "eat"、"tea" 和 "ate" 是一组变位词，"tan" 和 "nat" 是另一组变位词，而 "bat" 没有变位词，因此它自己为一组。

知识点

sort 方法可以用于排序数组中的元素。在 JavaScript 中，当你对一个字符串调用 split('') 方法时，它会将字符串分割成一个字符数组。例如，字符串 "eat" 会被分割成 ["e", "a", "t"]。

然后，当你对这个字符数组调用 sort() 方法时，它会根据字符的默认排序顺序（通常是按照 Unicode 码点）对数组中的元素进行排序。对于字母，这意味着它们会按照字母表的顺序进行排序。

例如：

"eat".split('').sort().join(''); // "aet"

在这个例子中，字符串 "eat" 被分割成 ["e", "a", "t"]，然后排序成 ["a", "e", "t"]，最后通过 join('') 方法重新组合成一个字符串 "aet"。

解释map.get(k).push(strs[i])

map.get(k):
- map 是一个 Map 对象，它存储键值对。
- k 是一个键，通常是通过某种方式（如前面提到的排序字符串）计算得到的。
- map.get(k) 方法用于获取与键 k 相关联的值。如果键 k 存在于 Map 中，它将返回与该键关联的值；如果键不存在，它将返回 undefined。
.push(strs[i]):
- push 是一个数组方法，用于将一个或多个元素添加到数组的末尾，并返回新的数组长度。
- strs[i] 是当前遍历到的字符串，其中 strs 是原始的字符串数组，i 是当前的索引。

功能描述

当执行 map.get(k).push(strs[i]) 时，首先通过 map.get(k) 获取与键 k 相关联的数组。
如果该键 k 已经存在于 map 中，那么 map.get(k) 将返回一个数组，然后 .push(strs[i]) 将当前字符串 strs[i] 添加到这个数组的末尾。
如果键 k 不存在，map.get(k) 返回 undefined，而 undefined 没有 push 方法，这将导致运行时错误。因此，通常在这之前会检查该键是否存在，或者使用 map.has(k) 来确保键存在。