每日一题——LeetCode 242:有效的字母异位词

简介: 每日一题——LeetCode 242:有效的字母异位词

LeetCode 242:有效的字母异位词

跳转题目点我-----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 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;
    }
}



目录
相关文章
|
4月前
|
存储 算法
LeetCode第49题字母异位词分组
LeetCode第49题"字母异位词分组"的解题方法,通过将每个字符串的字符排序后作为键存储在HashMap中,有效地将所有字母异位词分组。
LeetCode第49题字母异位词分组
|
2月前
|
存储
Leetcode第49题(字母异位词分组)
LeetCode第49题要求将字符串数组中的字母异位词分组,可以通过将每个字符串排序后作为键存入哈希表,最后将哈希表中的值添加到结果列表中来实现。
16 1
|
2月前
|
算法
Leetcode第十七题(电话号码的字母组合)
这篇文章介绍了如何使用深度优先搜索(DFS)算法来解决LeetCode第17题——电话号码的字母组合问题,通过递归方法生成所有可能的字母组合。
20 0
Leetcode第十七题(电话号码的字母组合)
|
2月前
|
索引
【LeetCode 11】242.有效的字母异位词
【LeetCode 11】242.有效的字母异位词
16 0
【LeetCode 11】242.有效的字母异位词
|
2月前
|
算法
【LeetCode 52】17.电话号码的字母组合
【LeetCode 52】17.电话号码的字母组合
32 0
|
4月前
|
算法
LeetCode第17题电话号码的字母组合
该文章介绍了 LeetCode 第 17 题电话号码的字母组合的解法,通过分析得出可使用递归和回溯的思想解决,避免循环穷举的高循环次数,并给出了具体的编码实现,同时总结了该题较难理解,需要了解递归的本质,当嵌套循环层次多时可考虑递归。
LeetCode第17题电话号码的字母组合
|
6月前
|
算法 容器
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
|
6月前
|
存储
力扣经典150题第四十二题:字母异位词分组
力扣经典150题第四十二题:字母异位词分组
36 0
|
6月前
|
存储
力扣经典150题第四十一题:有效的字母异位词
力扣经典150题第四十一题:有效的字母异位词
28 0
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行