【LeetCode刷题笔记（12-1）】【Python】【有效的字母异位词】【排序/字符统计】【简单】

引言

编写通过所有测试案例的代码并不简单，通常需要深思熟虑和理性分析。虽然这些代码能够通过所有的测试案例，但如果不了解代码背后的思考过程，那么这些代码可能并不容易被理解和接受。我编写刷题笔记的初衷，是希望能够与读者们分享一个完整的代码是如何在逐步的理性思考下形成的。我非常欢迎读者的批评和指正，因为我知道我的观点可能并不完全正确，您的反馈将帮助我不断进步。如果我的笔记能给您带来哪怕是一点点的启示，我也会感到非常荣幸。同时，我也希望我的分享能够激发您的灵感和思考，让我们一起在编程的道路上不断前行~

有效的字母异位词

题目描述

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

• 异位词：指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:

• 输入: s = “anagram”, t = “nagaram”
• 输出: true

示例 2:

• 输入: s = “rat”, t = “car”
• 输出: false

提示

• 1 <= s.length, t.length <= 5 * 10⁴
• s 和 t 仅包含小写字母

解决方案1：【排序】

根据题意，我们需要判断给定两个字符串 s 和 t 是否互为异位词。异位词是指由【相同字母】【重排列】形成的字符串。从异位词的定义中，我们可以得到两个推论：

1. 若 s 和 t 互为异位词， s 和 t 的字符个数必须相同 ⇒ len(s) == len(t) 必须恒成立；
2. 若 s 和 t 互为异位词，那么对s 和 t 分别进行字符串排序的结果必然一致；

完整代码如下：

class Solution:  
    def isAnagram(self, s: str, t: str) -> bool:  
        """  
        判断两个字符串是否为异位词。  
    
        Args:  
            s (str): 第一个字符串。  
            t (str): 第二个字符串。  
    
        Returns:  
            bool: 如果两个字符串是异位词，返回True；否则返回False。  
        """    
        # 获取字符串s的长度  
        s_len = len(s)  
        # 获取字符串t的长度  
        t_len = len(t)  
  
        # 如果两个字符串的长度不相等，一定不是异位词，直接返回False  
        if s_len != t_len:  
            return False  
  
        # 将字符串s的排序结果与排序后的字符串t进行比较，若一致，返回True，否则返回False  
        return "".join(sorted(s)) == "".join(sorted(t))

运行结果：

问题1：从运行结果来看，还存在一定的优化空间，代码哪些部分占用了大部分时间呢？

从时间复杂度上看，耗时最长的应当是对子串进行排序。假设字符串s的长度为N，那么字符串s进行排序的时间复杂度是O(NlogN)。如果N特别大，会非常耗时。

问题2：能不能在【不需要排序】的情况下，实现字母异位词的对比？

可以！突破局限，转换思路。

在上面的理性分析中，我们提出同时对字符串s和字符串t进行先排序后比较的策略，以验证字符串s与字符串p是否互为字母异位词。当字符串s的长度较小时，这么做无可厚非，但当字符串s的长度很大时，排序算法复杂度O(NlogN)的局限性就出现了。且题意告诉我们，1 <= s.length, t.length <= 5 * 10^4 ==> 字符串s的长度上限已经很大，排序算法顶不住了！

解决方案2：【字符统计】

问题3：还有哪些策略可以实现字母异位词的对比呢？

如果两个字符串互为字母异位词，既然它们的排序结果相同，那么每个字符的出现次数也必然相同。更重要的是，字母的个数是有限的(上限26个) ⇒ 我们可以使用两个长度为26的列表t_count和s_count，分别记录字符串s和t各个字母出现的次数。通过比较字符串s和t各个字母出现的次数，我们可以在O(N)时间复杂度下解决【有效的字母异位词】问题。

完整代码如下：

class Solution:  
    def isAnagram(self, s: str, t: str) -> bool:
        """  
        判断两个字符串是否为异位词。  
    
        Args:  
            s (str): 第一个字符串。  
            t (str): 第二个字符串。  
    
        Returns:  
            bool: 如果两个字符串是异位词，返回True；否则返回False。  
        """    
        # 检查两个字符串的长度是否相等  
        if len(s) != len(t):  
            return False  
  
        # 初始化计数数组，用于记录t和s中每个字符出现的次数  
        t_count = [0] * 26  # 26个字母的计数数组  
        s_count = [0] * 26  # 26个字母的计数数组  
  
        # 遍历t字符串和s字符串，并统计每个字符出现的次数  
        for i in range(len(t)):  
            t_count[ord(t[i]) - ord("a")] += 1  
            s_count[ord(s[i]) - ord("a")] += 1  
  
        # 返回t和s的字符计数是否相等  
        return t_count == s_count

运行结果：

复杂度分析

• 时间复杂度：O(N)，其中 N 是字符串s的长度。
  • 循环遍历t和s ===> O(N)
• 空间复杂度：O(N)
  • 需要用列表记录t和s中每个字符出现的次数 ===> O(N)

结束语

• 亲爱的读者，感谢您花时间阅读我们的博客。我们非常重视您的反馈和意见，因此在这里鼓励您对我们的博客进行评论。
• 您的建议和看法对我们来说非常重要，这有助于我们更好地了解您的需求，并提供更高质量的内容和服务。
• 无论您是喜欢我们的博客还是对其有任何疑问或建议，我们都非常期待您的留言。让我们一起互动，共同进步！谢谢您的支持和参与！
• 我会坚持不懈地创作，并持续优化博文质量，为您提供更好的阅读体验。
• 谢谢您的阅读！