题解 | #字母异位词的长度#

题目链接

题目描述

现有两个仅由小写英文字母构成的字符串 s 和 c，请判断它们是否为字母异位词。

字母异位词 的定义是：如果两个字符串中，每个字符出现的次数都完全相同，则称它们为字母异位词。

如果是字母异位词，输出它们的长度。
如果不是，返回 -1。

这是一个 核心代码模式 (Core Code Mode) 的题目，你只需要实现 isCongruent 函数。

示例 1: 输入:

"aba", "aa"

输出:

-1

说明: 两个字符串 b 出现的次数不同，不是字母异位词。

示例 2: 输入:

"a", "a"

输出:

说明: 两个字符串每个字符出现的次数都相同，是字母异位词，长度为1。

解题思路

判断两个字符串是否为字母异位词，核心是比较它们的字符构成是否完全相同。最高效的方法是统计每个字符串中各个字符出现的频率。

基本思路 - 字符计数法:

预检查: 字母异位词的一个基本前提是它们的长度必须相等。如果 s.length() != c.length()，它们绝不可能是异位词，可以直接返回 -1。这是一个重要的优化。
创建频率数组: 因为题目明确指出字符串仅由小写英文字母构成，我们可以创建一个大小为26的整型数组 counts，用来记录从 'a' 到 'z' 每个字符的出现频率。
统计: a. 遍历第一个字符串 s，对于遇到的每个字符 ch，将 counts 数组中对应位置的计数加一（即 counts[ch - 'a']++）。 b. 遍历第二个字符串 c，对于遇到的每个字符 ch，将 counts 数组中对应位置的计数减一（即 counts[ch - 'a']--）。
验证: 遍历 counts 数组。如果两个字符串是字母异位词，那么经过一加一减后，数组中的所有元素都应该归零。只要发现任何一个元素的计数不为0，就说明它们不是字母异位词，应返回 -1。
返回结果: 如果 counts 数组所有元素都为0，说明它们是字母异位词。此时，根据题意返回其中一个字符串的长度即可。

另一种思路 (排序法): 将两个字符串都转换成字符数组，然后对它们进行排序。如果排序后的结果完全相同，那么它们就是字母异位词。这种方法虽然直观，但时间复杂度为 $\mathcal{O}(L \log L)$ （L为字符串长度），效率低于字符计数法的 $\mathcal{O}(L)$ 。因此，我们优先采用字符计数法。

代码

cpp
java
python

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param s string字符串 
     * @param c string字符串 
     * @return int整型
     */
    int isCongruent(string s, string c) {
        if (s.length() != c.length()) {
            return -1;
        }

        vector<int> counts(26, 0);
        for (char ch : s) {
            counts[ch - 'a']++;
        }
        for (char ch : c) {
            counts[ch - 'a']--;
        }

        for (int count : counts) {
            if (count != 0) {
                return -1;
            }
        }
        
        return s.length();
    }
};

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param s string字符串 
     * @param c string字符串 
     * @return int整型
     */
    public int isCongruent(String s, String c) {
        if (s.length() != c.length()) {
            return -1;
        }

        int[] counts = new int[26];
        for (char ch : s.toCharArray()) {
            counts[ch - 'a']++;
        }
        for (char ch : c.toCharArray()) {
            counts[ch - 'a']--;
        }

        for (int count : counts) {
            if (count != 0) {
                return -1;
            }
        }
        
        return s.length();
    }
}

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @param c string字符串 
# @return int整型
#
class Solution:
    def isCongruent(self, s: str, c: str) -> int:
        if len(s) != len(c):
            return -1
        
        counts = [0] * 26
        # 使用 zip 可以一次遍历完成计数
        for char_s, char_c in zip(s, c):
            counts[ord(char_s) - ord('a')] += 1
            counts[ord(char_c) - ord('a')] -= 1
        
        # any() 函数可以高效地检查是否存在非零元素
        if any(count != 0 for count in counts):
            return -1
            
        return len(s)

算法及复杂度

算法: 字符计数 (Frequency Array)
时间复杂度: $\mathcal{O}(L)$ ，其中 $L$ 是字符串 s (或 c) 的长度。我们需要遍历字符串来填充和检查频率数组，数组大小是常数26。
空间复杂度: $\mathcal{O}(|\Sigma|)$ 或 $\mathcal{O}(1)$ ，其中 $|\Sigma|$ 是字符集的大小（本题中为26）。由于字符集大小是固定的，所以空间复杂度为常数。