242. 有效的字母异位词

Posted on | In
Words count in article: 612 | Reading time ≈ 2

题目

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

示例1：

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

示例2：

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

提示：

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

注意：

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

进阶

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

如果输入包含unicode字符的话，使用哈希表。如果使用数组的话，unicode范围过大，浪费空间

解法

解法一：

哈希表

借助哈希表，把s里面的每个字符，以及次数都保存在哈希表里面。遍历t，如果发现t中的字符c不在哈希表中， 则返回false，否则，字符c的次数减一。

如果字符c的次数减一完之后已经为0了，从哈希表中移除字符c。

Java-哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public boolean isAnagram(String s, String t) {
		if (null == s || null == t) {
			return false;
		}
		
		if (s.length() != t.length()) {
			return false;
		}
		
		Map<Character, Integer> map = new HashMap<Character, Integer>();
		for (char c : s.toCharArray()) {
			if (map.containsKey(c)) {
				map.put(c, map.get(c) + 1);
			} else {
				map.put(c, 1);
			}
		}
		
		for (char c : t.toCharArray()) {
			if (!map.containsKey(c)) {
				return false;
			} else {
				if (map.get(c) == 1) {
					map.remove(c);
				} else {
					map.put(c, map.get(c) - 1);
				}
			}
		}
		return true;
    }

解法二：

使用数组

声明一个26长度的数组，遍历s，对s中的每个c，对数组索引为c的位置自增。

遍历t，对t中的每个字符c，如果数组中对应位置的计数为0，返回false，否则自减一

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    int[] table = new int[26];
    for (int i = 0; i < s.length(); i++) {
        table[s.charAt(i) - 'a']++;
    }
    for (int i = 0; i < t.length(); i++) {
        table[t.charAt(i) - 'a']--;
        if (table[t.charAt(i) - 'a'] < 0) {
            return false;
        }
    }
    return true;
}

解法三：

排序

将字符串s和t转为字符数组，排序，挨个字符挨个字符比较

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean isAnagram(String s, String t) {
		if (null == s || null == t) {
			return false;
		}
		
		if (s.length() != t.length()) {
			return false;
		}
        char[] cs = s.toCharArray();
        char[] ct = t.toCharArray();
        Arrays.sort(cs);
        Arrays.sort(ct);
        for (int i = 0;i < cs.length;i++) {
        	if (cs[i] != ct[i]) {
        		return false;
        	}
        }
        return true;
    }
0%