Shouyu

Appearance

代码随想录 哈希表 242 字母的有效异位词 ​

题目链接：https://programmercarl.com/0242.有效的字母异位词.html

文章讲解：https://leetcode.cn/problems/valid-anagram/description/

题目描述 ​

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的 字母异位词。

示例 1:

text
输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

text
输入: s = "rat", t = "car"
输出: false

思路 ​

字母异位词，首先就是长度相等，这点 leetcode 默认已经实现了，我们不用再做判断。然后两个字符串是有相同的字母构成，并且只有出现的次数相同，但顺序可以不同。

暴力解法一 ​

  1. 检查两个字符串 s 和 t 的长度。如果长度不同，它们肯定不是字母异位词，直接返回 false。
  2. 将字符串 s 转换为字符数组并排序。使用 <algorithm> 内置的 sort 函数
  3. 将字符串 t 转换为字符数组并排序。
  4. 比较排序后的两个字符数组（或转换回字符串后比较）。如果它们相同，则返回 true，否则返回 false。

排序的算法时间复杂度一般是 O(N log N)，空间复杂度是 O(log N)。

暴力解法二 ​

上面的暴力解法不直观，我们可能最先想到的就是先遍历第一个字符串，然后内部，遍历第二个字符串。即对于字符串 s 中的每一个字符，都去字符串 t 里看看有没有使用过，如果没被使用过，那就记录一下，记录在哪里？新建一个字符串 t 长度的 bool 数组，在对应位置上标记一个"已使用过/一匹配），如果已被使用，那么继续寻找，如果遍历完了字符串 t 也没找到，那就可以不是字母异位词。这种方式其实是在"手动"统计和消耗字符的数量。每找到一个匹配，就把 t 里的那个字符标记为已用，防止重复使用。

哈希表法 ​

回顾暴力法，暴力法一告诉了我们多余的信息，就是排序。排序不仅告诉我们字符有哪些，还告诉我们它们的顺序。但对于字母异位词，我们只关心字符的种类和每种字符的数量是否相同，顺序是无关紧要的。

字母异位词的本质：每种字符出现的次数必须完全相同。

那么有两个核心要素我们需要记录，字符及其次数。我们需要一种数据结构来存储每个字符出现的次数。类似于 python 里面的那种字典吗？键值对结构？其实用不到。字符种类是有限的，26 个小写英文字母。

那么我们用一个固定大小的数组作为计数器。数组的索引对应字符（例如，索引 0 对应'a'，索引 1 对应'b'，...，索引 25 对应'z'），数组的值对应字符的出现次数。

这就是哈希表思想。核心思想是什么？

我们想记录元素以及元素出现的次数。

那能实现这个思想的很多了啊，数组（索引为元素，值为次数），map（key 为元素，value 为次数）。再简化一下，如果我们想记录元素以及元素有没有出现过，可以使用 set 集合，出现在集合中的元素就是出现过，没有就是没有。

ok，明白了我们想记录什么，开始吧。

遍历字符串 s，将出现的字符记录在数组索引中，出现的次数记录在值中。字符怎么转换到索引？因为索引是数字，字符本质上也是个整数，是一个 ASCII 上的整数。

ok，既然我们决定采用数组，那么我们对于每个字符串都建立一个数组计数器吗？然后比较这两个数组吗？其实不用，只需要建立一个数组，然后遍历第二个字符串的时候直接在已经建立好的数组计数器上进行计数就好了，最终全为 0 就是两者元素和元素出现的次数相同了。

步骤：

  • 步骤 1：初始化计数器。 创建一个大小为 26 的整数数组 counts，所有元素初始化为 0。

  • 步骤 2：统计第一个字符串 s 的字符。 遍历 s，对于每个字符 c，增加 counts[c - 'a'] 的值。

  • 步骤 3：核对第二个字符串 t 的字符。 遍历 t，对于每个字符 c，减少 counts[c - 'a'] 的值。

  • 步骤 4：检查最终计数。 遍历计数器数组 counts。如果所有计数都为 0，说明两个字符串是字母异位词，返回 true。否则，返回 false。

  • 优化/检查点 2：在开始计数之前，先比较两个字符串的长度。如果长度不同，它们不可能是字母异位词，直接返回 false。这可以避免不必要的计数操作。

时间复杂度：两次遍历字符串 O(n)，一次遍历数组 O(K)

空间复杂度：一个计数数组 O(K)

哈希表法其实是把"找字符"这件事用空间换时间，提前统计好，查找和消耗都变成了 O(1) 的操作。

cpp
bool isAnagram(string s, string t)
{
    int nums[26] = {0};
    for (int i = 0; i < s.size(); i++) // 计数器1
    {
        nums[s[i] - 'a']++;
    }
    for (int i = 0; i < t.size(); i++) // 计数器2
    {
        nums[t[i] - 'a']--;
    }
    for (int i = 0; i < 26; i++) //查看里面是否全为0
    {
        if (nums[i] != 0)
        {
            return false;
        }
    }
    return true;
};