LeetCode 242：有效的字母异位词

作者：武师叔

2022 年 7 月 16 日
本文字数：1694 字
阅读完需：约 6 分钟

跳转题目点我-----LeetCode 242

题意

给定字符串 s 和 t，判断两个字符串是否为字母异位词。

ps： s 和 t 中每个字符出现的次数都相同，则 s 和 t 互为字母异位词。

示例

输入：

s = "anagram", t = "nagaram"

复制代码

输出：

true

复制代码

题目解析

这道题字符串 s 和 t 仅包含小写字母，小写字母就固定的 26 个。

这种定长的范围且和字符次数相关，用哈希妥妥的没问题。

下面就是找出哈希函数，就是把每一个 key 对应到 0 ~ N-1 的范围内，并且放在合适的位置。

我们这里使用的哈希函数 f(key) = key - ‘a’ 。

这里其实是对字符 ASCII 的操作，字母 a ~ z 的 ASCII 是连续的 26 个数值。

比如 f(a) = 'a' - 'a' = 0，f(b) = 'b' - 'a' = 1，即字母 a 对应的是哈希表下标为 0 的位置，字母 b 对应的是哈希表下标为 1 的位置，剩下的依此类推。

哈希函数找好，下面的就很简单：

遍历字符串 s，哈希表对应的字符值加。
遍历字符串 t，哈希表对应的字符值减。
如果哈希表中的值都为 0，则 s 和 t 互为字母异位词。

具体的来看下面图解。

图解

在这以 s = "anagram", t = "nagaram" 为例。

首先初始化哈希表，根据哈希函数，字母 a ~ z 在哈希表中所占位置如下：

第一步，遍历字符串 s，碰到相应的字符，对应下标的哈希值 + 1。

对于 s = “anagram”，第 1 个字符为 a，a 对应哈希表下标为 0，则下标 0 对应值 +1：

#对于字符串 s，在对应位置加（比如出现 a，就在 a 的位置 +1）#ord()函数是Python中的一个库函数，用于从给定字符值中获取数字值，它接受一个字符并返回一个整数，即用于将字符转换为整数，即用于获取[ASCII]for i in range(len(s)):    hash[ord(s[i]) - ord('a')] += 1

复制代码

依次遍历完字符串 s，哈希表如下图：

第二步，遍历字符串 t，碰到对应的字符，相应下标的哈希值 -1。

对于 t = "nagaram"，第 1 个字符为 n，n 对应的下标为 13，则下标 13 对应的哈希值 -1：

#对于字符串 t，在对应位置减（比如出现 a，就在 a 的位置 -1）for i in range(len(t)):    hash[ord(t[i]) - ord('a')] -= 1

复制代码

同样，依次遍历完字符串 t，哈希表如下图：

第三步，遍历哈希表，所有的值均为 0，则 s 和 t 互为字母异位词，反之为否。

#遍历哈希表，如果值都为 0，则为字母异位词#如果存在任一值不为 0 的哈希值，则不为字母异位词for i in range(26):    if hash[i] != 0:                return Falsereturn True

复制代码

在此例中，字符串 s 和 t 互为字母异位词。

此题解法，时间复杂度为 O(n)，n 为 s 和 t 中较长的那个字符串的长度。

因为额外开了一个长为 26 的数组，所以空间复杂度为 O(m)，m = 26。

代码实现

Python 代码实现

class Solution:    def isAnagram(self, s: str, t: str) -> bool:        # 如果两个字符串长度不等，肯定不是字母异位词        if len(s) != len(t):            return False        # 如果两个字符串的长度相等        # 初始化哈希函数，字符串只包含小写字母，故初始化 26 个        hash = [0] * 26
        # 循环两个字符串        # 对于字符串 s，在对应位置加（比如出现 a，就在 a 的位置 +1）        for i in range(len(s)):            hash[ord(s[i]) - ord('a')] += 1
        # 对于字符串 t，在对应位置减（比如出现 a，就在 a 的位置 -1）        for i in range(len(t)):            hash[ord(t[i]) - ord('a')] -= 1                    # 遍历哈希表，如果值都为 0，则为字母异位词        # 如果存在任一值不为 0 的哈希值，则不为字母异位词        for i in range(26):            if hash[i] != 0:                return False
        return True

复制代码

Java 代码实现

class Solution {    public boolean isAnagram(String s, String t) {
        int[] record = new int[26];        for (char c : s.toCharArray()) {            record[c - 'a'] += 1;        }        for (char c : t.toCharArray()) {            record[c - 'a'] -= 1;        }        for (int i : record) {            if (i != 0) {                return false;            }        }        return true;    }}

复制代码

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/18e4cda452cb2eda7f851f0a4】。文章转载请联系作者。

武师叔

关注

每天丰富自己，去过自己想要的生活！ 2022.04.28 加入

一个喜欢最新技术，研发的人工智能专业的大二学生，用自己的代码做一些有意义的事情！目前大二结束有去大厂研发岗实习的计划，每天丰富自己的技术，去过自己想要的实习生活。

发布

暂无评论

创作场景

LeetCode 242：有效的字母异位词

题意

示例

题目解析

图解

代码实现

Python 代码实现

Java 代码实现

武师叔

评论