江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode第242题：有效的字母异位词

LeetCode第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. 首先检查两个字符串的长度是否相等，若不相等则直接返回 false
  2. 然后遍历第一个字符串，统计每个字符出现的次数
  3. 再遍历第二个字符串，减少对应字符的计数
  4. 最后检查所有字符的计数是否都为 0

对于仅包含小写字母的情况，我们可以使用一个长度为 26 的数组来替代哈希表，进一步优化空间使用。

代码实现

方法一：排序比较

C#实现

public class Solution {
    public bool IsAnagram(string s, string t) {
        if (s.Length != t.Length) {
            return false;
        }
        
        char[] sArray = s.ToCharArray();
        char[] tArray = t.ToCharArray();
        
        Array.Sort(sArray);
        Array.Sort(tArray);
        
        return new string(sArray) == new string(tArray);
    }
}

Python实现

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        
        return sorted(s) == sorted(t)

C++实现

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length()) {
            return false;
        }
        
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        
        return s == t;
    }
};

方法二：哈希表计数

C#实现

public class Solution {
    public bool IsAnagram(string s, string t) {
        if (s.Length != t.Length) {
            return false;
        }
        
        int[] counter = new int[26];
        
        // 统计第一个字符串中字符出现次数
        for (int i = 0; i < s.Length; i++) {
            counter[s[i] - 'a']++;
        }
        
        // 检查第二个字符串中字符出现次数
        for (int i = 0; i < t.Length; i++) {
            counter[t[i] - 'a']--;
            if (counter[t[i] - 'a'] < 0) {
                return false;
            }
        }
        
        // 所有计数器都应为0
        foreach (int count in counter) {
            if (count != 0) {
                return false;
            }
        }
        
        return true;
    }
}

Python实现

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        
        # 使用Counter计数
        from collections import Counter
        return Counter(s) == Counter(t)
        
        # 或者使用数组计数
        # counter = [0] * 26
        # for c in s:
        #     counter[ord(c) - ord('a')] += 1
        # for c in t:
        #     counter[ord(c) - ord('a')] -= 1
        #     if counter[ord(c) - ord('a')] < 0:
        #         return False
        # return all(count == 0 for count in counter)

C++实现

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length()) {
            return false;
        }
        
        vector<int> counter(26, 0);
        
        // 统计字符频率
        for (char c : s) {
            counter[c - 'a']++;
        }
        
        // 验证字符频率
        for (char c : t) {
            counter[c - 'a']--;
            if (counter[c - 'a'] < 0) {
                return false;
            }
        }
        
        return true;
    }
};

性能分析

方法一：排序比较

  • 时间复杂度：O(n log n)，其中 n 是字符串的长度。排序的时间复杂度是 O(n log n)，比较两个字符串的时间复杂度是 O(n)，总的时间复杂度是 O(n log n)。
  • 空间复杂度：O(n)，排序需要额外的空间。

方法二：哈希表计数

  • 时间复杂度：O(n)，其中 n 是字符串的长度。我们需要遍历两个字符串各一次。
  • 空间复杂度：O(1)，因为我们使用了固定大小的数组（对于只包含小写字母的情况是 26）。如果考虑 Unicode 字符，空间复杂度会变为 O(k)，其中 k 是可能出现的字符数量。

方法对比

方法 时间复杂度 空间复杂度 优势 劣势
排序比较 O(n log n) O(n) 实现简单 效率较低
哈希表计数 O(n) O(1)或O(k) 效率高 需要额外空间

进阶问题解决方案

对于包含 Unicode 字符的情况，我们可以将方法二中的定长数组替换为哈希表（字典），以适应更广泛的字符集：

def isAnagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    
    char_count = {}
    
    # 统计第一个字符串中字符出现次数
    for c in s:
        char_count[c] = char_count.get(c, 0) + 1
    
    # 检查第二个字符串中字符出现次数
    for c in t:
        if c not in char_count or char_count[c] == 0:
            return False
        char_count[c] -= 1
    
    return True

常见错误与陷阱

  1. 忘记检查长度：不同长度的字符串不可能是字母异位词，应首先检查长度。
  2. 忽略字符频率：只检查字符是否存在而不检查频率是不够的。
  3. 未考虑大小写：如果题目没有明确说明，应考虑字符的大小写是否敏感。

相关题目