华为 OD 训练营 · 题解精讲

LC242. 有效的字母异位词

LC242. 有效的字母异位词视频地址。

题目描述

给定两个字符串 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 的数组中（注意题目的说明） YxuAbPFcno1RcuxsN3IcMjnTnPb.png

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

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

参考代码

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

← 上一篇

LeetCode232、用栈实现队列

LC283. 移动零