242.有效的字母异位词

题目:242.有效的字母异位词

给定两个字符串 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 * 10^4
s 和 t 仅包含小写字母

• 进阶：

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

思路1

1. 长度检查：

   • 如果 s 和 t 的长度不同，直接返回 false，因为它们不可能是字母异位词。

2. 字符计数：

   • 使用一个哈希表 charCount 来记录每个字符的出现次数。遍历 s 字符串。记录 s 中每个字符的出现次数。

3. 检查t中的字符：

   • 遍历 t 字符串，检查每个字符是否在 t 中出现足够次数。
   • 如果字符在 t 中出现，计数 -1。当字符计数等于 0 时，在哈希表中移除此字符。

4. 返回结果：

   • 当哈希表为空，代表所有字符都能满足条件，返回 true。

• 时间复杂度:O(n)
• 空间复杂度:O(n)

代码

public boolean isAnagram(String s, String t) {
    // 如果两个字符串的长度不相等，它们不可能是字母异位词
    if (s.length() != t.length()) {
        return false;
    }
    // 使用哈希表来统计每个字符的出现次数
    Map<Character, Integer> charCount = new HashMap<>();
    // 遍历s，统计每个字符的出现次数
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        charCount.put(c, charCount.getOrDefault(c, 0) + 1);
    }
    for (int i = 0; i < t.length(); i++) {
        char c = t.charAt(i);
        // 如果字符在t中出现，计数-1。当字符计数等于0时，在哈希表中移除此字符
        if (charCount.computeIfPresent(c, (key, value) -> value - 1) != null && charCount.get(c) == 0) {
            charCount.remove(c);
        }
        // 当哈希表为空，代表所有字符都能满足条件，返回true
        if (charCount.isEmpty()) {
            return true;
        }
    }
    return false;
}

思路2

1. 长度检查：

   • 如果 s 和 t 的长度不同，直接返回 false，因为它们不可能是字母异位词。

2. 字符计数：

   • 使用一个数组 charCount 来记录每个字符的出现次数。遍历 s 字符串。记录 s 中每个字符的出现次数。
   • 如果某个字符不在 charCount 中，或者出现次数不足，则返回 false。
   • 如果某个字符可以满足需求，减少其在 count 中的计数。

3. 返回结果：

   • 如果所有字符都能满足需求，则返回 true。

• 时间复杂度:O(m+n)
• 空间复杂度:O(1)

代码

public boolean isAnagram(String s, String t) {
    // 如果两个字符串的长度不相等，它们不可能是字母异位词
    if (s.length() != t.length()) {
        return false;
    }
    int[] charCount = new int[26];
    for (int i = 0; i < s.length(); i++) {
        charCount[s.charAt(i) - 'a']++;
    }
    for (int i = 0; i < t.length(); i++) {
        if (--charCount[t.charAt(i) - 'a'] < 0) {
            return false;
        }
    }
    return true;
}