ACM 选手图解力扣之有效的字母异位词!

简介: ACM 选手图解力扣之有效的字母异位词!

大家好呀,我是你们的蛋蛋。


今天解决有效的字母异位词,哈希表实战系列第一道题。


话不多说,直接开整。

640.png


   LeetCode 242:有效的字母异位词



题意


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


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


示例



输入:s = "anagram", t = "nagaram"

输出:true

提示


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


题目解析


水题,难度简单,题目倒是挺唬人。


到这种类似什么字符出现次数啥的,如果没有思路了,都可以往哈希的思路上便一下。


关于哈希表,如果小婊贝们不懂的话,可以看我下面这篇文章,包会:


ACM 选手带你玩转哈希表!


再来看关键点,这道题字符串 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 在哈希表中所占位置如下:

640.png


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


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

640.png

# 对于字符串 s,在对应位置加(比如出现 a,就在 a 的位置 +1)
for i in range(len(s)):
    hash[ord(s[i]) - ord('a')] += 1


依次遍历完字符串 s,哈希表如下图:


640.png

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


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

640.png

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

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


640.png


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


# 遍历哈希表,如果值都为 0,则为字母异位词
# 如果存在任一值不为 0 的哈希值,则不为字母异位词
for i in range(26):
    if hash[i] != 0:
                return False
return 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;
    }
}



图解字母异位词到这就结束辣,这是哈希表实战系列第一道题,算是开胃菜。


AC 不是目的,目的是好好去琢磨琢磨这种解题方法,然后能运用到之后的题目中。


有问题可以留言区留言,记得帮我点赞在看呀,么么哒。


我是帅蛋,我们下次见。

相关文章
|
19天前
|
算法 容器
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
|
23天前
|
存储 算法 安全
LeetCode 题目 49:字母异位词分组 5种算法实现与典型应用案例【python】
LeetCode 题目 49:字母异位词分组 5种算法实现与典型应用案例【python】
|
4天前
|
存储
力扣经典150题第四十二题:字母异位词分组
力扣经典150题第四十二题:字母异位词分组
5 0
|
4天前
|
存储
力扣经典150题第四十一题:有效的字母异位词
力扣经典150题第四十一题:有效的字母异位词
4 0
|
19天前
|
算法
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
|
19天前
|
算法
【经典LeetCode算法题目专栏分类】【第8期】滑动窗口:最小覆盖子串、字符串排列、找所有字母异位词、 最长无重复子串
【经典LeetCode算法题目专栏分类】【第8期】滑动窗口:最小覆盖子串、字符串排列、找所有字母异位词、 最长无重复子串
|
23天前
|
存储 算法 数据挖掘
leetcode第十七题:解密电话号码的字母组合与应用【python】
leetcode第十七题:解密电话号码的字母组合与应用【python】
|
27天前
|
存储 算法 Java
【经典算法】LeetCode 1170:比较字符串最小字母出现频次(Java/C/Python3实现含注释说明,中等)
【经典算法】LeetCode 1170:比较字符串最小字母出现频次(Java/C/Python3实现含注释说明,中等)
16 0
|
18天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
18天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题