【算法千题案例】⚡️每日LeetCode打卡⚡️——63. 有效的字母异位词
【算法千题案例】⚡️每日LeetCode打卡⚡️——63. 有效的字母异位词
呆呆敲代码的小Y
发布于 2021-10-29 10:30:04
发布于 2021-10-29 10:30:04
文章被收录于专栏：呆呆敲代码的小Y 公众号
前言
原题样例：有效的字母异位词
请添加图片描述
算法题 |
|---|
- 每天打卡一道算法题，既是一个学习过程，又是一个分享的过程
- 提示：本专栏解题 编程语言一律使用 C# 和 Java 两种进行解题
- 要保持一个每天都在学习的状态，让我们一起努力成为算法大神吧！
- 今天是力扣算法题持续打卡第63天！
算法题 |
|---|
原题样例：有效的字母异位词
给定两个字符串 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 仅包含小写字母
C#方法：一次遍历
对比下标数组是否一致，用于检测两字符串同构。
代码：
public class Solution {
public bool IsIsomorphic(string s, string t)
{
List<int> indexS = new List<int>();
List<int> indexT = new List<int>();
for (int i = 0; i < s.Length; i++)
indexS.Add(s.IndexOf(s[i]));
for (int j = 0; j < t.Length; j++)
indexT.Add(t.IndexOf(t[j]));
return indexS.SequenceEqual(indexT);
}
}执行结果
通过
执行用时：72 ms，在所有 Java 提交中击败了82.28%的用户
内存消耗：39 MB，在所有 Java 提交中击败了7.60%的用户Java 方法一：排序
思路解析
- t 是 s 的异位词等价于「两个字符串排序后相等」。因此我们可以对字符串 s 和 t 分别排序，看排序后的字符串是否相等即可判断。
- 此外，如果 s 和 t 的长度不同，t 必然不是 s 的异位词。
代码：
class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
char[] str1 = s.toCharArray();
char[] str2 = t.toCharArray();
Arrays.sort(str1);
Arrays.sort(str2);
return Arrays.equals(str1, str2);
}
}执行结果
通过
执行用时：3 ms，在所有 Java 提交中击败了74.73%的用户
内存消耗：38.5 MB，在所有 Java 提交中击败了67.34%的用户复杂度分析
时间复杂度：O( nlogn )
空间复杂度：O( long n )Java 方法二：哈希
思路解析
- t 是 s 的异位词等价于「两个字符串中字符出现的种类和次数均相等」。
- 由于字符串只包含 26个小写字母，因此我们可以维护一个长度为 26 的频次数组 table，先遍历记录字符串 s 中字符出现的频次，然后遍历字符串 t，减去 table 中对应的频次，如果出现table[i]<0，则说明 t 包含一个不在 s 中的额外字符，返回 false 即可。
代码：
class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
char[] str1 = s.toCharArray();
char[] str2 = t.toCharArray();
Arrays.sort(str1);
Arrays.sort(str2);
return Arrays.equals(str1, str2);
}
}执行结果
通过
执行用时：4 ms，在所有 Java 提交中击败了45.11%的用户
内存消耗：38.5 MB，在所有 Java 提交中击败了73.10%的用户复杂度分析
时间复杂度：O( nlogn )
空间复杂度：O( long n )总结
- 今天是力扣算法题打卡的第六十三天！
- 文章采用
C#和Java两种编程语言进行解题 - 一些方法也是参考力扣大神写的，也是边学习边分享，再次感谢算法大佬们
- 那今天的算法题分享到此结束啦，明天再见！
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021/10/27 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
