14 | 面试题：有效的字母异位词-算法面试通关 50 讲

当前位置:　首页>> 技术小册>> 算法面试通关 50 讲

### 14 | 面试题：有效的字母异位词

在算法面试中，字符串问题是一类常见且极具挑战性的题目，它们不仅考验了面试者的编程基础，还对其逻辑思维能力和问题解决策略提出了高要求。其中，“有效的字母异位词”是一个既经典又富有启发性的面试题，它要求我们判断两个字符串是否包含完全相同的字符集合，且每个字符出现的次数也相同，但顺序可以不同。这类问题在编程竞赛、日常编程任务以及面试中频繁出现，掌握其解法对于提升算法能力至关重要。

#### 一、问题定义

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

- **输入**：两个字符串 `s` 和 `t`。
- **输出**：布尔值，表示 `t` 是否为 `s` 的字母异位词。

#### 二、问题分析

要解决这个问题，我们可以从以下几个角度进行思考：

1. **字符种类与数量**：首先，两个字符串必须是等长的，或者它们包含完全相同的字符集合但数量可能不同（但在此问题中，由于要求是字母异位词，所以长度必须相等）。这意味着我们需要统计每个字符串中各个字符的出现次数。

2. **排序法**：一种直观的方法是将两个字符串排序，然后直接比较排序后的字符串是否相等。如果相等，则它们是字母异位词。这种方法的时间复杂度主要取决于排序算法的选择，通常是 O(nlogn)，其中 n 是字符串的长度。

3. **哈希表法**：另一种更高效的方法是使用哈希表（如 Python 中的字典）来记录每个字符在字符串中出现的次数。首先遍历第一个字符串，统计每个字符的出现次数并存储在哈希表中；然后遍历第二个字符串，对哈希表中的计数进行增减操作（如果字符存在则减一，否则无法成为字母异位词）。最后，检查哈希表中所有值是否都为零，如果是，则两个字符串是字母异位词。这种方法的时间复杂度为 O(n)，其中 n 是字符串的长度，因为它只涉及到两次遍历和哈希表的基本操作。

#### 三、解法实现

##### 1. 排序法实现

```python
def isAnagram_Sort(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    sorted_s = sorted(s)
    sorted_t = sorted(t)
    return sorted_s == sorted_t
```

这段代码首先检查两个字符串的长度是否相等，如果不等则直接返回 `False`。然后，它分别对两个字符串进行排序，并比较排序后的结果是否相同。如果相同，则返回 `True`，表示 `t` 是 `s` 的字母异位词；否则返回 `False`。

##### 2. 哈希表法实现

```python
def isAnagram_Hash(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    char_count = {}
    
    # 统计 s 中字符的出现次数
    for char in s:
        if char in char_count:
            char_count[char] += 1
        else:
            char_count[char] = 1
    
    # 根据 t 更新 char_count 中的计数
    for char in t:
        if char in char_count:
            char_count[char] -= 1
        else:
            return False
    
    # 检查所有计数是否都为零
    for count in char_count.values():
        if count != 0:
            return False
    
    return True
```

或者，我们可以使用 Python 的 `collections.Counter` 来简化哈希表的使用：

```python
from collections import Counter

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

这段代码利用了 `Counter` 类，它会自动统计字符串中每个字符的出现次数，并允许我们直接比较两个字符串的字符计数是否相同。

#### 四、性能分析

- **排序法**：时间复杂度为 O(nlogn)，空间复杂度为 O(logn)（主要由排序算法决定，如快速排序的栈空间使用）或 O(n)（如果考虑排序后字符串的存储）。这种方法在字符串长度不是特别大时通常足够高效，但不如哈希表法优雅。

- **哈希表法**：时间复杂度为 O(n)，空间复杂度也为 O(n)（用于存储字符计数）。这种方法在处理大数据集时更加高效，因为它避免了不必要的排序操作。

#### 五、扩展思考

- **大小写敏感性问题**：题目中未明确说明是否考虑大小写敏感性。如果考虑大小写敏感，则直接按照上述方法实现即可；如果不考虑，可以在统计字符前将所有字符转换为小写（或大写）。

- **非字母字符处理**：如果字符串中包含非字母字符（如数字、标点符号等），并且题目要求忽略这些字符，则需要在统计字符前进行过滤处理，只保留字母字符。

- **空间优化**：虽然哈希表法在大多数情况下已经足够高效，但如果对空间有极其严格的要求，可以考虑使用固定大小的数组来替代哈希表（假设字符集大小有限且已知，如 ASCII 字符集中的小写字母只有 26 个）。

- **实际应用**：字母异位词的概念不仅限于字符串处理，还可以扩展到其他领域，如密码学中的置换密码分析、生物信息学中的基因序列比较等。

通过深入分析“有效的字母异位词”这一问题，我们不仅掌握了多种解决方法，还学会了如何在不同场景下灵活选择最适合的算法。这种能力对于提升编程素养和应对复杂问题至关重要。

该分类下的相关小册推荐：

编程之道-算法面试(下)

编程之道-算法面试(上)

数据结构与算法(下)

业务开发实用算法精讲

数据结构与算法之美

数据结构与算法(中)

数据结构与算法(上)