Fork me on GitHub

leetcode之242. 有效的字母异位词

发表于 | 分类于
字数统计 325 字 | 阅读时长 1 分钟

题目描述：

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

示例 1:

1
2
3
> 输入: s = "anagram", t = "nagaram"
> 输出: true
>

示例 2:

1
2
3
> 输入: s = "rat", t = "car"
> 输出: false
>

说明:
你可以假设字符串只包含小写字母。

进阶:
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

解题思路一：

时间复杂度：$O(nlogn)$, 空间复杂度:$O(1)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.size() != t.size())
        {
            return false;
        }
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        for(int i = 0; i < s.size(); ++i)
        {
            if(s[i] != t[i])
            {
                return false;
            }
        }
        return true;
    }
};

解题思路二：

时间复杂度：$O(n)​$, 空间复杂度:$O(1)​$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool isAnagram(string s, string t) {
        vector<int> count1(26,0);
        vector<int> count2(26,0);
        for(char c : s)
        {
            count1[c-'a']++;
        }
        for(char k : t)
        {
            count2[k-'a']++;
        }
        for(int i=0; i<26; i++)
        {
            if(count1[i]!=count2[i])
            {
                return false;
            }
        }
        return true;
    }
};

解题思路三：

时间复杂度：$O(n)$, 空间复杂度:$O(1)$.

1
2
3
4
5
6
7
class Solution {
public:
    bool isAnagram(string s, string t) {
        
        return multiset<char>(s.begin(), s.end() ) == multiset<char>(t.begin(), t.end() );
    }
};