Leetcode-242-有效的字母异位词

Leecode-242-有效的字母异位词

题目描述

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1:

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


示例 2:

输入: s = "rat", t = "car"
输出: false

说明:
你可以假设字符串只包含小写字母。

进阶:
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

方法一：排序

思路：

• 通过将s字符串转换成char数组
• 对每个字符进行排序。
• 因此，如果T是S的异位词，对两个字符串进行排序将产生两个相同的字符串。
• 此外，如果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);

        // O（n）
        return Arrays.equals(str1,str2);
    }
}

• 复杂度分析
  • 时间复杂度：O(nlogn) ，排序的成本是O(nlogn) ，比较字符串的成本是O(n),所以总体的时间复杂度是O(nlogn)
  • 空间复杂度：O(n) ,toCharArray() 制作了一个字符串的拷贝，所以它花费 O(n)额外的空间

方法二：哈希表

思路：

• 为了检查t是否是s的重新排列，我们只需要计算两个字符串中对应字母出现的次数是否相同即可
• 因为S和T都只包含26个小写字母，所以哈希表大小26个字母就够了
• 这里需要两个计数器来进行比较吗？
  • 答：不需要，只需要一个计数器表即可。用一个计数器表计算s字母的频率，用t减少计数器表中每个字母的计数器，然后检查计数器是否回到了0。

• 这里直接用数组代替hash，减少哈希碰撞带来的复杂度。

class Solution {
    // 哈希表
    // 为了检查t是否是s的重新排列,我们可以计算两个字符串每个字母的出现次数并比较
    // 因为s和t都只包含A-Z的字母，所欲偶一一个简单的26位计数器就够了
    // 我们需要两个计数器进行比较吗？ 
    // 答： 是不需要的,因为我们可以用一个计数器计算s字母的频率,用t减少计数器表中每个字母的计数器,最后检查计数器是否回到了0
    public boolean isAnagram(String s, String t) {
        // 1. 长度不等直接返回
        if(s.length() != t.length()){
            return false;
        }

        // 2. 统计s出现的频率,并且用t减少计数器
        int[] counter = new int[26];
        for(int i = 0;i < s.length();i++){
            counter[s.charAt(i) - 'a']++;
            counter[t.charAt(i) - 'a']--;
        }

        // 3. 判断最后26个字母 是否每一位都归0了
        for(int count:counter){
            if(count != 0){
                return false;
            }
        }

        // 4. 检查完毕 返回true
        return true;
    }
}

• 时间复杂度：O(n) 遍历两个字符串的开销
• 空间复杂度： O(1)

打赏