leetcode242. 有效的字母异位词，哈希表

leetcode242. 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:
输入: s = “anagram”, t = “nagaram”
输出: true

示例 2:
输入: s = “rat”, t = “car”
输出: false

提示:
1 <= s.length, t.length <= 5 * 104
s 和 t 仅包含小写字母

题目分析

给定两个字符串 s 和 t，判断 t 是否是 s 的字母异位词。字母异位词是指由相同字母重排列形成的字符串。这个问题可以通过哈希表（或称为字典）来解决。

算法步骤

1. 初始化一个无序哈希表 p。
2. 遍历字符串 s，将每个字符的出现次数存储在哈希表中。
3. 遍历字符串 t，减少哈希表中对应字符的出现次数。
4. 遍历哈希表 p，检查每个字符的出现次数是否为0。
5. 如果所有字符的出现次数都为0，则返回 true，表示 t 是 s 的字母异位词；否则返回 false。

算法流程

具体代码

class Solution {
public:
    bool isAnagram(string s, string t) {
    unordered_map<char,int> p;
    for(int i=0;i<s.size();i++)
    {
        p[s[i]]++;
    }
    for(int i=0;i<t.size();i++)
    {
        p[t[i]]--;
    }
    for(auto q:p)
    {
        if(q.second!=0) return false;
    }
    return true;
    }
};

算法分析

• 时间复杂度: O(n)，其中 n 是字符串 s 和 t 的长度之和。
• 空间复杂度: O(1)，因为哈希表的大小只取决于字符集的大小，对于英文字母而言，其大小是固定的。
• 易错点: 在处理字符出现次数时，需要注意字符的ASCII值范围，确保所有字符都能被正确处理。

相似题目