跳至主要內容

LeetCode 242、有效的字母异位词

LeetCode 242、有效的字母异位词

视频地址。

https://uha.xet.tech/s/3ev2qz

一、题目描述

给定两个字符串 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 * 104
  • s 和 t 仅包含小写字母

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

二、题目解析

题目讲的是让你判断两个字符串中的字母是否一致，比如 示例1 中，s 包含字母 a、n、g、r、m，而 t 中也包含 a、n、g、r、m ，都是只有这五个字母，并且 频次 相同，只是顺序不同。

看到 频次 这个词，你脑海中第一想法是什么？

没错，就是 哈希表 ！

解法思路很简单。

1、首先先判断两个字符串长度是否相同，不相同直接返回 false

2、然后把 s 中所有的字符出现个数使用 计数器 统计起来，存入一个大小为 26 的数组中（注意题目的说明）

img
img

3、最后再来统计 t 字符串，即遍历 t 时将对应的字母频次进行减少，如果期间 计数器 出现小于零的情况，则说明 t 中包含一个不存在于 s 中的字母，直接返回 false。

img
img

4、最后检查计数器是否归零。

三、参考代码

代码一

哈希集合调API讨巧解法

# 题目：LC242. 有效的字母异位词
# 难度：简单
# 作者：闭着眼睛学数理化
# 算法：哈希集合调API讨巧解法
# 代码看不懂的地方，请直接在群上提问

# 导入collections中的Counter计数器类
from collections import Counter

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return Counter(s) == Counter(t)
        
# 直接获得s和t的计数结果Counter(s)和Counter(t)
# 若两者相等，说明s和t中的元素以及频率完全一致，互为字母异位词
# 若两者不相等，说明s和t中的元素以及频率不完全一致，不是一组有效的字母异位词

代码二

哈希集合遍历解法

# 题目：LC242. 有效的字母异位词
# 难度：简单
# 作者：闭着眼睛学数理化
# 算法：哈希集合遍历解法
# 代码看不懂的地方，请直接在群上提问

# 导入collections中的Counter计数器类
from collections import Counter

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        # 如果两个字符串长度不同，必然不可能构成一组有效的字母异位词，返回False
        if len(s) != len(t):    
            return False
        # 使用Counter()计数器，得到两个字符串对应的哈希表
        cnt1, cnt2 = Counter(s), Counter(t)
        # 遍历cnt1中的键（即某个特定字符）
        for ch in cnt1:
            # 如果这个字符在cnt1中的频率和在cnt2中的频率不相等
            if cnt1[ch] != cnt2[ch]:
                # 返回False
                return False
        # 如果在上述循环中没有返回False，说明这两个字符串互为字母异位词
        return True

代码三

用列表表示哈希表进行统计

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 有效的字母异位词（LeetCode 242）：https://leetcode.cn/problems/valid-anagram/
class Solution {
    public boolean isAnagram(String s, String t) {

        // 如果两个字符串的长度都不一致，那么肯定是无法成为字母异位词的
        if(s.length() != t.length()){

            // 直接返回 false
            return false;

        }

        // 让 a - z 这 26 个字母对应的下标变成 0 - 25 方便存到数组中
        // 比如 a 对应的索引就是 0 
        // b 对应的索引就是 1
        int[] table = new int[26];

        // 从头到尾遍历字符串 s
        for( int i = 0 ; i < s.length() ; i++){

            // 把访问的字符转换为整数的形式
            // 比如访问字母 a，那么 -'a' 之后就是 0，就是 a 对应的索引为 0 
            int index = s.charAt(i) - 'a';

            // 那么意味着这个字母出现的频次需要加 1
            table[index]++;

        }

        for( int i = 0 ; i < t.length() ; i++){

            // 把访问的字符转换为整数的形式
            // 比如访问字母 a，那么 -'a' 之后就是 0，就是 a 对应的索引为 0 
            int index = t.charAt(i) - 'a';

            // 那么意味着这个字母出现的频次需要减 1 
            table[index]--;

            // 如果说发现这个字母出现的频次小于了 0 
            // 说明 t 中出现了 s 中不曾用的字母
            if(table[index] < 0){

                // 那就不是字母异位词
                return false;

            }

        }

        // 否则，说明是字母异位词
        return true;

    }
}

2、C++ 代码

class Solution {
public:
    bool isAnagram(string s, string t) {
        // 如果两个字符串的长度都不一致，那么肯定是无法成为字母异位词的
        if(s.length() != t.length()){

            // 直接返回 false
            return false;

        }

        // 让 a - z 这 26 个字母对应的下标变成 0 - 25 方便存到数组中
        // 比如 a 对应的索引就是 0 
        // b 对应的索引就是 1
        vector<int> table(26, 0);

        // 从头到尾遍历字符串 s
        for( int i = 0 ; i < s.length() ; i++){

            // 把访问的字符转换为整数的形式
            // 比如访问字母 a，那么 -'a' 之后就是 0，就是 a 对应的索引为 0 
            int index = s[i] - 'a';

            // 那么意味着这个字母出现的频次需要加 1
            table[index]++;

        }

        for( int i = 0 ; i < t.length() ; i++){

            // 把访问的字符转换为整数的形式
            // 比如访问字母 a，那么 -'a' 之后就是 0，就是 a 对应的索引为 0 
            int index = t[i] - 'a';

            // 那么意味着这个字母出现的频次需要减 1 
            table[index]--;

            // 如果说发现这个字母出现的频次小于了 0 
            // 说明 t 中出现了 s 中不曾用的字母
            if(table[index] < 0){

                // 那就不是字母异位词
                return false;

            }

        }

        // 否则，说明是字母异位词
        return true;
    }
};

3、Python 代码

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        
        # 如果两个字符串的长度都不一致，那么肯定是无法成为字母异位词的
        if len(s) != len(t):
            # 直接返回 False
            return False

        # 让 a - z 这 26 个字母对应的下标变成 0 - 25 方便存到数组中
        # 比如 a 对应的索引就是 0 
        # b 对应的索引就是 1
        table = [0] * 26

        # 从头到尾遍历字符串 s
        for i in s:

            # 把访问的字符转换为整数的形式
            # 比如访问字母 a，那么 -'a' 之后就是 0，就是 a 对应的索引为 0 
            index = ord(i) - ord('a')

            # 那么意味着这个字母出现的频次需要加 1
            table[index] += 1


        for i in t:

            # 把访问的字符转换为整数的形式
            # 比如访问字母 a，那么 -'a' 之后就是 0，就是 a 对应的索引为 0 
            index = ord(i) - ord('a')

            # 那么意味着这个字母出现的频次需要减 1 
            table[index] -= 1

            # 如果说发现这个字母出现的频次小于了 0 
            # 说明 t 中出现了 s 中不曾用的字母
            if table[index] < 0 : 

                # 那就不是字母异位词
                return False


        # 否则，说明是字母异位词
        return True

4、C代码

#include <stdbool.h>
#include <string.h>

bool isAnagram(char *s, char *t) {
    // 如果两个字符串的长度不一致，则直接返回 false
    if (strlen(s) != strlen(t)) {
        return false;
    }

    // 记录 a - z 字母的出现频次
    int table[26] = {0};

    // 遍历字符串 s，统计字母出现的频次
    for (int i = 0; s[i] != '\0'; i++) {
        int index = s[i] - 'a'; // 字母对应的下标
        table[index]++;
    }

    // 遍历字符串 t，减去对应字母的频次
    for (int i = 0; t[i] != '\0'; i++) {
        int index = t[i] - 'a'; // 字母对应的下标
        table[index]--;

        // 如果频次小于 0，说明 t 中有 s 没有的字母
        if (table[index] < 0) {
            return false;
        }
    }

    // 如果没有问题，返回 true
    return true;
}

5、Node JavaScript代码

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
    // 如果两个字符串长度不同，直接返回 false
    if (s.length !== t.length) {
        return false;
    }

    // 创建一个数组记录 a-z 的频次
    const table = new Array(26).fill(0);

    // 遍历字符串 s，统计字母频次
    for (let char of s) {
        const index = char.charCodeAt(0) - 'a'.charCodeAt(0);
        table[index]++;
    }

    // 遍历字符串 t，减去字母的频次
    for (let char of t) {
        const index = char.charCodeAt(0) - 'a'.charCodeAt(0);
        table[index]--;

        // 如果频次小于 0，说明 t 中有 s 没有的字母
        if (table[index] < 0) {
            return false;
        }
    }

    // 如果没有问题，返回 true
    return true;
};

6、Go代码

func isAnagram(s string, t string) bool {
    // 如果两个字符串长度不同，直接返回 false
    if len(s) != len(t) {
        return false
    }

    // 创建一个数组记录 a-z 的频次
    table := make([]int, 26)

    // 遍历字符串 s，统计字母频次
    for _, char := range s {
        index := char - 'a'
        table[index]++
    }

    // 遍历字符串 t，减去字母的频次
    for _, char := range t {
        index := char - 'a'
        table[index]--

        // 如果频次小于 0，说明 t 中有 s 没有的字母
        if table[index] < 0 {
            return false
        }
    }

    // 如果没有问题，返回 true
    return true
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 为 s 的长度。
  • 空间复杂度：O(S)，其中 S 为字符集大小，此处 S = 26 。
本站内容包括机考真题解析、八股文速记、技术&行为面试指南、真实上岸经验与截图墙。
Copyright © 2025 欧弟算法