【算法千题案例】⚡️每日LeetCode打卡⚡️——63. 有效的字母异位词

@TOC

📢前言

• 🌲 每天打卡一道算法题，既是一个学习过程，又是一个分享的过程😜
• 🌲 提示：本专栏解题 编程语言一律使用 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 两种编程语言进行解题
• 一些方法也是参考力扣大神写的，也是边学习边分享，再次感谢算法大佬们
• 那今天的算法题分享到此结束啦，明天再见！