数组、set、map,数组是比较高效查找的
判断字符串 s
和 t
是否互为字母异位词。如果它们包含相同的字符且每个字符出现的次数也相同,那么它们互为字母异位词。
长度检查:
if (s.length !== t.length) return false;
如果 s
和 t
的长度不相等,它们不可能是字母异位词,直接返回 false
。
初始化计数器数组:
const resSet = new Array(26).fill(0);
const base = "a".charCodeAt();
resSet
是一个长度为 26 的数组,用于存储每个小写字母的出现次数(假设 s
和 t
只包含小写字母)。base
存储了字母 'a' 的 ASCII 码值,用于将字母转换为数组索引。统计 s
中字符出现次数:
for (const i of s) { resSet[i.charCodeAt() - base]++; }
遍历字符串 s
,使用 charCodeAt()
函数获取每个字符的 ASCII 码值,然后根据 base
计算出索引,增加 resSet
中相应位置的计数。
验证 t
中的字符:
for (const i of t)
{ if (!resSet[i.charCodeAt() - base]) return false;
resSet[i.charCodeAt() - base]--; }
t
,对于每个字符,检查 resSet
中对应位置的计数。如果计数为 0,则表示 t
中有一个在 s
中不存在的字符,或者字符出现次数不匹配,返回 false
。resSet
中相应位置的计数。返回结果:
return true;
果代码执行到这里,说明 s
和 t
是字母异位词,返回 true
。
这个函数通过计数每个字符的出现次数,来判断两个字符串是否互为字母异位词。由于只用了一个固定长度的数组,它在处理只包含小写字母的字符串时非常高效。
示例 1: 输入 ["eat", "tea", "tan", "ate", "nat", "bat"]
初始化哈希表:
Map
对象 map
。遍历字符串数组:
对于每个字符串 str
在数组 ["eat", "tea", "tan", "ate", "nat", "bat"]
中,执行以下步骤:
"eat":
"eat" -> ["e", "a", "t"] -> ["a", "e", "t"] -> "aet"
map.has("aet")
返回 false
(因为 "aet" 还不在 map
中),所以执行 map.set("aet", [])
并添加 "eat" 到 "aet" 键对应的数组中。"tea":
"tea"
排序后变为 "aet"
。map.has("aet")
返回 true
(因为 "aet" 已存在),所以直接将 "tea" 添加到 "aet" 键对应的数组中。"tan":
"tan"
排序后变为 "ant"
。map.has("ant")
返回 false
,所以执行 map.set("ant", [])
并添加 "tan" 到 "ant" 键对应的数组中。"ate":
"ate"
排序后也是 "aet"
。"nat":
"nat"
排序后变为 "ant"
。"bat":
"bat"
排序后变为 "abt"
。map.has("abt")
返回 false
,所以执行 map.set("abt", [])
并添加 "bat" 到 "abt" 键对应的数组中。提取并返回结果:
Array.from(map.values())
将 map
中的所有值(即分组后的字符串数组)转换为一个数组。[["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
。函数 groupAnagrams
将每个字符串按字母排序后,使用排序结果作为键来分组所有字母异位词。最终返回的数组包含了分组好的字母异位词数组,每个子数组包含所有字符集相同的原始字符串。在这个例子中,"eat"、"tea" 和 "ate" 互为字母异位词,因此它们被分组在一起,同理可得其他分组。
初始化两个计数器数组:pCount
和 sCount
分别用于存储 p
和窗口内字符串的字符计数。
遍历 p
:对 p
中的每个字符进行计数。
滑动窗口:遍历字符串 s
,同时更新 sCount
数组来计算窗口内各字符的出现次数。
窗口大小与 p
相等时:比较 sCount
和 pCount
。如果两者完全一致,将左指针的位置加入结果数组。
移动窗口:右指针每向右移动一次,左指针也相应地向右移动一次,以保持窗口大小不变。
这种方法通过在 s
上滑动一个固定大小的窗口并比较字符出现次数,有效地找出了所有 p
的异位词的起始索引。
?