How do I check if two strings are anagrams?

You can check if two strings are anagrams by either comparing their sorted versions or by counting the frequency of characters using a hash table.

What are the time and space complexities for 'Valid Anagram'?

Using hashing, the time complexity is O(n) and space complexity is O(1) (ignoring the character set size). Sorting has a time complexity of O(n log n).

Can I solve the 'Valid Anagram' problem with constant space?

Yes, by using an array of size 26 to count characters, you can achieve O(1) space complexity.

Why is sorting sometimes slower for this problem?

Sorting is O(n log n), which can be slower than O(n) hashing, especially for large inputs, making hashing a better choice for efficiency.

What is the primary pattern for solving this problem?

The problem follows a Hash Table plus String pattern, where you either count characters using a hash map or use sorting to compare the strings.

#242

Easy

auto_awesome哈希·表·结合·string

LeetCode 题解工作台

有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。示例 1: 输入: s = "anagram", t = "nagaram" 输出: true 示例 2: 输入: s = "rat", t = "car" 输出: false 提示: 1 4 s 和 t 仅包含小…

哈希表字符串排序

题目描述

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

示例 1:

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

示例 2:

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

提示:

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

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

lightbulb

解题思路

方法一：计数

我们先判断两个字符串的长度是否相等，如果不相等，说明两个字符串中的字符肯定不同，返回 false。

否则，我们用哈希表或者一个长度为 $26$ 的数组来记录字符串 $s$ 中每个字符出现的次数，然后遍历另一个字符串 $t$ ，每遍历到一个字符，就将哈希表中对应的字符次数减一，如果减一后的次数小于 $0$ ，说明该字符在两个字符串中出现的次数不同，返回 false。如果遍历完两个字符串后，哈希表中的所有字符次数都为 $0$ ，说明两个字符串中的字符出现次数相同，返回 true。

时间复杂度 $O(n)$ ，空间复杂度 $O(C)$ ，其中 $n$ 是字符串的长度；而 $C$ 是字符集的大小，本题中 $C=26$ 。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        cnt = Counter(s)
        for c in t:
            cnt[c] -= 1
            if cnt[c] < 0:
                return False
        return True

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Looking for efficient solutions using hashing or sorting.
question_mark
Expect optimization in terms of space or time based on input constraints.
question_mark
Can test with edge cases like large inputs to evaluate performance.

warning

常见陷阱

外企场景

error
Using a hash table can lead to excessive space usage for large inputs.
error
Sorting may cause performance issues with strings near the upper length limit.
error
Overcomplicating the solution with unnecessary operations or data structures.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Use an extended character set, e.g., Unicode, to test solution robustness.
arrow_right_alt
Change the problem to ignore case or spaces.
arrow_right_alt
Implement case-sensitive anagram checks.

help

常见问题

外企场景

继续练习

#389 找不同 #49 字母异位词分组 #451 根据字符出现频率排序