LeetCode: 242. Valid Anagram

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

Example:

Input: s = "anagram", t = "nagaram"
Output: true

Input: s = "rat", t = "car"
Output: false

问题

给定两个字符串 s 和 t，如果 t 是 s 的字母异位词，则返回 true，否则返回 false。

解决方案 1

使用字符计数来判断两个字符串是否为字母异位词

Approach 1 / 方法 1

通过统计两个字符串中每个字符的出现次数来判断它们是否为字母异位词。如果两个字符串中所有字符的出现次数都相同，那么它们就是字母异位词。

通过 collections.Counter 统计字符出现频率，并比较两个字符串的字符频率表。

Detailed Steps / 详细步骤

Initialization / 初始化:

1. Import Counter from collections
   从 collections 导入 Counter

Step 1 / 第一步:

2. Create Counter objects for both strings s and t
   为字符串 s 和 t 创建 Counter 对象

Step 2 / 第二步:

3. Compare the two Counter objects
   比较两个 Counter 对象

Implementation / 实现

python

from collections import Counter

def isAnagram(s: str, t: str) -> bool:
    return Counter(s) == Counter(t)

Explanation / 解释

1. Step 1 / 第一步:

• Counter counts the frequency of each character in s and t
Counter 统计字符串 s 和 t 中每个字符的频率

2. Step 2 / 第二步:

• The function returns True if both Counter objects are equal, indicating t is an anagram of s
  如果两个 Counter 对象相等，则函数返回 True，表示 t 是 s 的字母异位词

Complexity Analysis / 复杂度分析

• Time Complexity: O(n), where n is the length of the strings
  时间复杂度: O(n)，其中 n 是字符串的长度

• Space Complexity: O(1), since the Counter will have at most 26 characters (assuming only lowercase English letters)
  空间复杂度: O(1)，因为 Counter 最多有 26 个字符（假设只有小写英文字母）

Key Concept / 关键概念

• Using a hash map to count character frequencies
  使用哈希表统计字符频率

解决方案 2

排序字符串并比较

Approach 2 / 方法 2

将两个字符串排序，然后比较排序后的结果。如果两个字符串排序后的结果相同，则它们是字母异位词。

Detailed Steps / 详细步骤

Initialization / 初始化:

1. Import the sorted function
   导入 sorted 函数

Step 1 / 第一步:

2. Sort both strings s and t
   对字符串 s 和 t 进行排序

Step 2 / 第二步:

3. Compare the sorted strings
   比较排序后的字符串

Implementation / 实现

python

def isAnagram(s: str, t: str) -> bool:
    return sorted(s) == sorted(t)

Explanation / 解释

1. Step 1 / 第一步:

• Sort the characters in s and t
  对字符串 s 和 t 进行字符排序

2. Step 2 / 第二步:

• The function returns True if the sorted strings are identical, indicating t is an anagram of s
  如果排序后的字符串相同，则函数返回 True，表示 t 是 s 的字母异位词

Complexity Analysis / 复杂度分析

• Time Complexity: O(n log n), where n is the length of the strings due to sorting
  时间复杂度: O(n log n)，其中 n 是字符串的长度，因为需要排序

• Space Complexity: O(n), due to the space required for sorting
  空间复杂度: O(n)，因为排序需要额外的空间

Key Concept / 关键概念

• Sorting the strings and comparing
  排序字符串并比较

解决方案 3

使用哈希表进行字符计数

Approach 3 / 方法 3

创建一个哈希表来记录字符串 s 中每个字符的频率，然后遍历字符串 t 来减少相应字符的频率。如果所有频率最终都为0，则 t 是 s 的字母异位词。

Detailed Steps / 详细步骤

Initialization / 初始化:

1. Create a frequency dictionary for s
   为 s 创建一个频率字典

Step 1 / 第一步:

2. Iterate over each character in s and increment its count in the dictionary
   遍历 s 中的每个字符，并在字典中增加相应字符的计数

Step 2 / 第二步:

3. Iterate over each character in t and decrement its count in the dictionary
   遍历 t 中的每个字符，并在字典中减少相应字符的计数

Step 3 / 第三步:

4. Check if all values in the dictionary are zero
   检查字典中的所有值是否都为零

Implementation / 实现

python

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

    char_count = {}

    for char in s:
        char_count[char] = char_count.get(char, 0) + 1

    for char in t:
        if char not in char_count or char_count[char] == 0:
            return False
        char_count[char] -= 1

    return all(value == 0 for value in char_count.values())

Explanation / 解释

1. Step 1 / 第一步:

• Initialize the frequency dictionary for s
  初始化 s 的频率字典

2. Step 2 / 第二步:

• Increment the frequency count for each character in s
  增加 s 中每个字符的频率计数

3. Step 3 / 第三步:

• Decrement the frequency count for each character in t
  减少 t 中每个字符的频率计数

4. Step 4 / 第四步:

• Check if all values in the dictionary are zero
  检查字典中的所有值是否都为零

Complexity Analysis / 复杂度分析

• Time Complexity: O(n), where n is the length of the strings
  时间复杂度: O(n)，其中 n 是字符串的长度

• Space Complexity: O(1), assuming the character set is fixed (e.g., lowercase English letters)
  空间复杂度: O(1)，假设字符集是固定的（例如，小写英文字母）

Key Concept / 关键概念

• Using a hash table to count character frequencies and ensure they match
  使用哈希表统计字符频率并确保它们匹配

Tips / 提示

• Use Counter for a simpler implementation, or manually manage a frequency dictionary for more control
  使用 Counter 实现更简单，或手动管理频率字典以获得更多控制

Solution Template for similar questions / 提示

• Compare frequency of characters or use hash tables for anagram-related problems
  对于字母异位词相关问题，比较字符频率或使用哈希表

What does the main algorithm of this question aim to test? / 这个问题的主要算法旨在测试什么？

Understanding of character frequency counting and hash table usage
理解字符频率统计和哈希表的使用

5 more similar questions / 推荐5问题

1. LeetCode 49. Group Anagrams
2. LeetCode 383. Ransom Note
3. LeetCode 567. Permutation in String
4. LeetCode 438. Find All Anagrams in a String
5. LeetCode 125. Valid Palindrome

More

• LeetCode Discuss
• LeetCode Explore
• GeeksforGeeks
• Stack Overflow