有效的字母异位词

发表于 分类于 阅读次数：

有效的字母异位词（难度：简单）

1

方法一：哈希表

思路
  • 首先判断两个字符串长度是否相等，不相等则直接返回 false。
  • 若相等，则初始化 26 个字母哈希表，遍历字符串 s 和 t
  • s 负责在对应位置增加，t 负责在对应位置减少，如果哈希表的值都为 0，则二者是字母异位词
复杂度

时间复杂度：O(n)。 空间复杂度：O(1)。尽管我们使用了额外的空间，但是空间的复杂性是 O(1)，因为无论 N 有多大，表的大小都保持不变。

代码

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length())
            return false;

        int[] alpha = new int[26];
        for(int i = 0; i < s.length(); i++){
            alpha[s.charAt(i) - 'a']++;
            alpha[t.charAt(i) - 'a']--;
        }

        for(int i : alpha){
            if(i!=0)
                return false;
        }
        return true;
    }
}
4

方法二：排序

复杂度

时间复杂度：O(nlogn)。

空间复杂度：O(1)，空间取决于排序实现，如果使用 heapsort，通常需要 O(1)辅助空间。

代码
1
2
3
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return sorted(s) == sorted(t)
3

方法三：利用Python中的set()

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        
        set1 = set(s)
        set2 = set(t)

        for i in set1:
            if i not in set2:
                return False

        for i in set2:
            if i not in set1:
                return False
        
        for i in set1:
            if s.count(i) != t.count(i):
                return False
        
        return True
2