LeetCode第242题:有效的字母异位词

题目描述:

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

示例 1:

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

输入: s = "rat", t = "car"
输出: false
说明:
你可以假设字符串只包含小写字母。

解法1:

算法:

首先判断s和t长度是否相等,如果不相等则返回false,如果相等可以对两个字符串进行排序,如果两者是字母异位词,排序之后的结果应该相等。

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);
    }

复杂度分析:

时间复杂度:排序成本O(nlogn),比较成本O(n),所以总体时间复杂度为O(nlogn)

空间复杂度:取决于排序实现,java中实现了字符串的拷贝,所以需要花费O(n)的额外空间

解法2:

算法:

因为只有小写字母,所以总共为26个字母,可以用一个长度为26的数组来实现,对于s的每一个字符,都让数组中该字符对应的位置+1,t的每一个字符-1,如果最后整个数组全部为0,返回true。

public boolean isAnagram(String s,String t){
        if (s.length() != t.length()){
            return false;
        }
        //总共26位字母
        int[] counter = new int[26];
        for (int i = 0; i < s.length(); i++) {
            //和'a'做差的结果即在数组中的索引
            counter[s.charAt(i) - 'a']++;
            counter[t.charAt(i) - 'a']--;
        }
        //如果数组全为0,返回true,否则返回false
        for (int i = 0; i < 26; i++) {
            if (counter[i] != 0){
                return false;
            }
        }
        return true;
    }

复杂度分析:

时间复杂度:O(n)

空间复杂度:O(1)

进阶:

如果输入字符串包含Unicode字符怎么办?

使用哈希表来实现而不是固定大小的计数器,因为Unicode字符范围超过100万,哈希表是一种更通用的解决办法

原文地址:https://www.cnblogs.com/jordan95225/p/13276418.html