LeetCode LCR 032. 有效的字母异位词

Categories:

题目描述
思路分析
1. 解法一：哈希表（数组计数）（推荐）
2. 解法二：排序
相似题目

题目描述

✅ LCR 032. 有效的字母异位词

思路分析

解法一：哈希表（数组计数）（推荐）

核心思路：

字母异位词的本质是：两个字符串包含完全相同的字母，且每个字母出现次数相同。

用一个长度为 26 的整数数组作为哈希表，记录每个字母的频次差值。

遍历 s，对对应字母的计数 +1；遍历 t，对对应字母的计数 -1。

最后检查数组中所有值是否为 0，若全为 0 则互为字母异位词。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串的长度，遍历两次字符串。

空间复杂度：O(1)，固定大小为 26 的计数数组，与输入规模无关。

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }

        // 用长度为 26 的数组记录各字母频次差值
        int[] count = new int[26];

        // 遍历 s，对应字母计数 +1；遍历 t，对应字母计数 -1
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++;
            count[t.charAt(i) - 'a']--;
        }

        // 所有计数为 0，说明两字符串字母频次完全一致
        for (int c : count) {
            if (c != 0) {
                return false;
            }
        }

        return true;
    }
}

func isAnagram(s string, t string) bool {
    if len(s) != len(t) {
        return false
    }

    // 用长度为 26 的数组记录各字母频次差值
    var count [26]int

    // 遍历 s，对应字母计数 +1；遍历 t，对应字母计数 -1
    for i := 0; i < len(s); i++ {
        count[s[i]-'a']++
        count[t[i]-'a']--
    }

    // 所有计数为 0，说明两字符串字母频次完全一致
    for _, c := range count {
        if c != 0 {
            return false
        }
    }

    return true
}

解法二：排序

核心思路：

将两个字符串各自排序，若两个字符串互为字母异位词，则排序后的结果必然相同。

直接比较排序后的字符串是否相等即可。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示字符串的长度，排序的时间复杂度为 O(n log n)。

空间复杂度：O(n)，排序需要 O(n) 的额外空间存储字符数组。

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }

        // 将字符串转为字符数组并排序
        char[] sChars = s.toCharArray();
        char[] tChars = t.toCharArray();
        Arrays.sort(sChars);
        Arrays.sort(tChars);

        // 排序后字符数组相等则互为字母异位词
        return Arrays.equals(sChars, tChars);
    }
}

func isAnagram(s string, t string) bool {
    if len(s) != len(t) {
        return false
    }

    // 将字符串转为字节切片并排序
    sBytes := []byte(s)
    tBytes := []byte(t)
    sort.Slice(sBytes, func(i, j int) bool { return sBytes[i] < sBytes[j] })
    sort.Slice(tBytes, func(i, j int) bool { return tBytes[i] < tBytes[j] })

    // 排序后字节切片相等则互为字母异位词
    return string(sBytes) == string(tBytes)
}

相似题目

题目	难度	考察点
49. 字母异位词分组	中等	哈希表、字符串分组
438. 找到字符串中所有字母异位词	中等	滑动窗口、哈希表
383. 赎金信	简单	哈希表、字符频次统计
567. 字符串的排列	中等	滑动窗口、字符频次
266. 回文排列	简单	哈希表、字符频次
1002. 查找共用字符	简单	哈希表、字符频次统计

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/50102030