跳到主要内容

有效的字母异位词

· 阅读需 5 分钟
Eureka X
Eureka X
Mr.Nobody

力扣面试经典——242题​

💡 参考代码：​

/**
 * 判断两个字符串是否为字母异位词
 * 字母异位词定义：两个字符串包含相同的字符，且每个字符出现次数相同
 * 
 * @param s 第一个字符串
 * @param t 第二个字符串
 * @return true 表示是字母异位词，false 表示不是
 */
bool isAnagram(char * s, char * t) {
    // 获取两个字符串的长度
    int len_s = strlen(s);
    int len_t = strlen(t);
    
    // 如果长度不同，肯定不是字母异位词
    if (len_s != len_t) {
        return false;
    }
    
    // 创建哈希表，用于统计字符出现次数（只考虑小写字母a-z）
    int count[26] = {0};
    
    // 遍历两个字符串，统计字符出现次数的差异
    for (int i = 0; i < len_s; i++) {
        count[s[i] - 'a']++;    // s中字符出现则计数+1
        count[t[i] - 'a']--;    // t中字符出现则计数-1
    }
    
    // 检查所有字符的计数是否都为0
    // 如果是字母异位词，则每个字符在两个字符串中出现次数相同，计数为0
    for (int i = 0; i < 26; i++) {
        if (count[i] != 0) {
            return false;
        }
    }
    
    return true;
}

📖 总结：​

点击展开题目总结

🤔 有效的字母异位词

1️⃣ 题目核心信息​

🎯 功能描述：判断两个字符串是否为字母异位词（包含相同字符且每个字符出现次数相同）

📥 输入输出：

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

2️⃣ 实现原理​

💡 核心思路：使用字符计数法，统计每个字符在两个字符串中出现次数的差异

📋 实现步骤：

  1. 比较两个字符串长度，不同则直接返回 false
  2. 创建大小为26的数组用于记录字符出现次数差异
  3. 遍历字符串，对 s 中字符计数+1，对 t 中字符计数-1
  4. 检查所有字符计数是否都为0，是则为字母异位词

3️⃣ 关键点解析​

🎯 代码技巧​

  • 使用数组代替哈希表提高效率（针对小写字母）
  • 同时遍历两个字符串，减少一次遍历
  • 利用字符与 'a' 的差值作为数组索引

4️⃣ 使用场景​

✅ 适用情况：​

  • 判断两个单词是否由相同字母组成
  • 字母频率统计相关问题
  • 字符串相似性比较

⚠️ 前提条件：​

  • 输入字符串只包含小写字母（基础版本）
  • 字符串长度有限制范围

5️⃣ 复杂度分析​

  • ⏱️ 时间复杂度：O(n)，其中 n 是字符串长度，需要遍历一次字符串
  • 💾 空间复杂度：O(1)，只使用了固定大小的数组

6️⃣ 注意事项​

🚩 边界情况：​

  • 空字符串或单字符情况
  • 长度不同的字符串
  • 完全相同的字符串

💥 易错点：​

  • 忘记先比较字符串长度
  • 数组大小设置错误（应为26）
  • 字符转索引时计算错误

7️⃣ 补充说明​

以 s = "anagram" 和 t = "nagaram" 为例：

步骤 1: 长度检查​

len_s = strlen("anagram") = 7
len_t = strlen("nagaram") = 7
// 长度相等，继续执行

步骤 2: 初始化计数数组​

int count[26] = {0};  // 所有元素初始化为0
// count = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

步骤 3: 遍历字符串并更新计数​

逐个字符处理：

is[i]t[i]s[i]-'a't[i]-'a'count[s[i]-'a']count[t[i]-'a']
0'a''n'013count[0]++count[13]--
1'n''a'130count[13]++count[0]--
2'a''g'06count[0]++count[6]--
3'g''a'60count[6]++count[0]--
4'r''r'1717count[17]++count[17]--
5'a''a'00count[0]++count[0]--
6'm''m'1212count[12]++count[12]--

处理过程中的 count 数组变化：

初始:     [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
i=0后:    [1,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0]
i=1后:    [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
i=2后:    [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0]
i=3后:    [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
i=4后:    [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
i=5后:    [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
i=6后:    [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

步骤 4: 检查最终结果​

// 遍历 count 数组检查是否全为0
for (int i = 0; i < 26; i++) {
    if (count[i] != 0) {
        return false;  // 如果有任何元素不为0，则不是字母异位词
    }
}
// 所有元素都为0，返回 true
return true;

结果​

函数返回 true，表示 "anagram" 和 "nagaram" 是字母异位词，结果正确。

这个过程展示了算法如何通过字符计数的方式判断两个字符串是否包含完全相同的字符和数量，从而确定它们是否为字母异位词

加载评论中...