每日一练(44):有效的字母异位词

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

给定两个字符串 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 仅包含小写字母


来源:力扣(LeetCode)


链接:https://leetcode-cn.com/probl...


方法一:排序


思路分析


t 是 s 的异位词等价于「两个字符串排序后相等」。因此我们可以对字符串 s 和 t 分别排序,看排序后的字符串是否相等即可判断。此外,如果 s 和 t 的长度不同,t 必然不是 s 的异位词。


bool isAnagram(string s, string t) {
    if (s.length() != t.length()) {
        return false;
    }
    sort(s.begin(), s.end());
    sort(t.begin(), t.end());
    return s == t;
}


方法二:哈希表


思路分析


由于字符串只包含 26 个小写字母,因此我们可以维护一个长度为 26 的频次数组 table,先遍历记录字符串 s 中字符出现的频次,然后遍历字符


串 t,减去 table 中对应的频次,如果出现 table[i]<0,则说明 tt 包含一个不在 s 中的额外字符,返回 false 即可


bool isAnagram(string s, string t) {
    if (s.length() != t.length()) {
        return false;
    }
    vector<int> table(26, 0);
    for (auto &ch : s) {
        table[ch - 'a']++;
    }
    for (auto &ch : t) {
        table[ch - 'a']--;
        if (table[ch - 'a'] < 0) {
            return false;
        }
    }
    return true;
}


目录
相关文章
|
8月前
|
Java C++ Python
leetcode-242:有效的字母异位词
leetcode-242:有效的字母异位词
54 0
|
3月前
|
索引
【LeetCode 11】242.有效的字母异位词
【LeetCode 11】242.有效的字母异位词
24 0
【LeetCode 11】242.有效的字母异位词
|
7月前
|
存储
力扣经典150题第四十一题:有效的字母异位词
力扣经典150题第四十一题:有效的字母异位词
40 0
|
7月前
|
JavaScript 前端开发 Java
leetcodet题解:242.有效的字母异位词
leetcodet题解:242.有效的字母异位词
32 0
|
8月前
leetcode代码记录(有效的字母异位词
leetcode代码记录(有效的字母异位词
36 1
|
8月前
【力扣】242. 有效的字母异位词
【力扣】242. 有效的字母异位词
|
8月前
LeetCode 242. 有效的字母异位词
LeetCode 242. 有效的字母异位词
46 0
|
C++ 索引
有效的字母异位词(力扣刷题)
有效的字母异位词(力扣刷题)
|
算法 索引
LeetCode每日1题--有效的字母异位词
LeetCode每日1题--有效的字母异位词
75 0
|
存储 算法 Java
LeetCode:242. 有效的字母异位词
给定两个字符串s和t,编写一个函数来判断 t 是否是 s 的字母异位词。 注意:若 s 和 t 中每个字符出现的次数都相同,则称 s 和 t 互为字母异位词。