剑指 Offer II 032. 有效的变位词

题目链接

剑指 Offer II 032. 有效的变位词 easy

题目描述

给定两个字符串 s和 t，编写一个函数来判断它们是不是一组变位词（字母异位词）。

注意：若 s和 t中每个字符出现的次数都相同且字符顺序不完全相同，则称 s和 t互为变位词（字母异位词）。

示例 1:

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

示例 2:

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

示例 3:

输入: s = “a”, t = “a”
输出: false

提示：

• $1<=s.length,t.length<=5\ast 10^4$
• s和 t仅包含小写字母

解法一：排序

时间复杂度：$O(n\ast logn)$

C++代码：

class Solution {
public:
    bool isAnagram(string s, string t) {
        //如果 s 直接和 t 相等 那也不符合要求
        if(s == t) return false;
        //将 s 和 t 按字典序从小到大排序 如果 s == t 说明 s 和 t 互为 字母异位词
        sort(s.begin(),s.end());
        sort(t.begin(),t.end());
        return s == t;
    }
};

解法二：计数

用一个数组 cnt[26]，对于s中出现的字符，每次 +1。对于 t中出现的字符，每次 -1。最后判断 cnt[]的每一个位置上的数是否为 0即可。

时间复杂度：$O(n)$

C++代码：

class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.size() != t.size() || s == t) return false;

        int cnt[26] = {0};

        for(auto c:s) cnt[c - 'a']++;
        for(auto c:t) cnt[c - 'a']--;

        for(int i = 0;i < 26;i++){
            if(cnt[i] != 0) return false;
        }
        return true;
    }
};

Python代码：

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return s != t and Counter(s) == Counter(t)