【12.29】转行小白历险记-刷算法05

2023-12-30 05:04:42

242.有效的字母异位词

数组、set、map,数组是比较高效查找的

函数功能

判断字符串 st 是否互为字母异位词。如果它们包含相同的字符且每个字符出现的次数也相同,那么它们互为字母异位词。

代码逻辑

  1. 长度检查

    if (s.length !== t.length) return false;

    如果 s t 的长度不相等,它们不可能是字母异位词,直接返回 false

  2. 初始化计数器数组

    const resSet = new Array(26).fill(0); 
    const base = "a".charCodeAt();
    • resSet 是一个长度为 26 的数组,用于存储每个小写字母的出现次数(假设 st 只包含小写字母)。
    • base 存储了字母 'a' 的 ASCII 码值,用于将字母转换为数组索引。
  3. 统计 s 中字符出现次数

    for (const i of s) { resSet[i.charCodeAt() - base]++; }

    遍历字符串 s使用 charCodeAt() 函数获取每个字符的 ASCII 码值,然后根据 base 计算出索引,增加 resSet 中相应位置的计数。

  4. 验证 t 中的字符

    for (const i of t) 
    { if (!resSet[i.charCodeAt() - base]) return false; 
    resSet[i.charCodeAt() - base]--; }
    • 遍历字符串 t,对于每个字符,检查 resSet 中对应位置的计数。如果计数为 0,则表示 t 中有一个在 s 中不存在的字符,或者字符出现次数不匹配,返回 false
    • 减少 resSet 中相应位置的计数。
  5. 返回结果

    return true;

    果代码执行到这里,说明 st 是字母异位词,返回 true

总结

这个函数通过计数每个字符的出现次数,来判断两个字符串是否互为字母异位词。由于只用了一个固定长度的数组,它在处理只包含小写字母的字符串时非常高效。

49字母异位词

示例 1: 输入 ["eat", "tea", "tan", "ate", "nat", "bat"]

  1. 初始化哈希表

    • 创建一个空的 Map 对象 map
  2. 遍历字符串数组

    • 对于每个字符串 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"
        • 再次将 "ate" 添加到 "aet" 键对应的数组中。
      • "nat"

        • "nat" 排序后变为 "ant"
        • 将 "nat" 添加到 "ant" 键对应的数组中。
      • "bat"

        • "bat" 排序后变为 "abt"
        • map.has("abt") 返回 false,所以执行 map.set("abt", []) 并添加 "bat" 到 "abt" 键对应的数组中。
  3. 提取并返回结果

    • 使用 Array.from(map.values())map 中的所有值(即分组后的字符串数组)转换为一个数组。
    • 返回的数组是:[["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

结果解释

函数 groupAnagrams 将每个字符串按字母排序后,使用排序结果作为键来分组所有字母异位词。最终返回的数组包含了分组好的字母异位词数组,每个子数组包含所有字符集相同的原始字符串。在这个例子中,"eat"、"tea" 和 "ate" 互为字母异位词,因此它们被分组在一起,同理可得其他分组。

438.找到字符串中所有字母异位词?

  1. 初始化两个计数器数组pCountsCount 分别用于存储 p 和窗口内字符串的字符计数。

  2. 遍历 p:对 p 中的每个字符进行计数。

  3. 滑动窗口:遍历字符串 s,同时更新 sCount 数组来计算窗口内各字符的出现次数。

  4. 窗口大小与 p 相等时:比较 sCountpCount。如果两者完全一致,将左指针的位置加入结果数组。

  5. 移动窗口:右指针每向右移动一次,左指针也相应地向右移动一次,以保持窗口大小不变。

这种方法通过在 s 上滑动一个固定大小的窗口并比较字符出现次数,有效地找出了所有 p 的异位词的起始索引。

?

文章来源:https://blog.csdn.net/TTTT2222111/article/details/135289517
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。