LeetCode_排序_中等_242.有效的字母异位词

目录

• 1.题目
• 2.思路
• 3.代码实现（Java）

1.题目

给定两个字符串 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 仅包含小写字母

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

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/valid-anagram

2.思路

（1）排序

（1.1）先判断字符串s和t的长度是否相等，若不相等则直接返回false，否则继续下一步；

（1.2）使用toCharArray()方法将字符串s和t分别转换为其对应的字符数组schars和tchars；

（1.3）使用sort()方法对字符数组进行排序，然后再将它们转换为字符串；

（1.4）最后返回equals()方法比较的结果即可。

（2）哈希表

（2.1）先判断字符串s和t的长度是否相等，若不相等则直接返回false，否则继续下一步；

（2.2）定义长度为26的数组map，用来存储字符串s中的各个字符的个数，下标0对应字符a，下标1对应字符b…，依此类推；

（2.3）先遍历字符串s，将其所包含的字符个数情况保存到数组map中。然后再遍历字符串t，每扫描到一个字符就先将map中该字符的个数减一，然后再判断该字符的个数是否小于0，若小于0，则说明t不是s的字母异位词，直接返回false，否则继续遍历；

（2.4）若在遍历字符串t的过程中没有直接返回false，则说明t是s的字母异位词，最后返回true即可。

3.代码实现（Java）

//（1）排序
public boolean isAnagram(String s, String t) {
    if(s.length()!=t.length()){
        return false;
    }
    //把字符串转化成字符数组
    char[] schars=s.toCharArray();
    char[] tchars=t.toCharArray();
    //对字符数组进行排序
    Arrays.sort(schars);
    Arrays.sort(tchars);
    //把字符数组转换为字符串
    String sorteds=new String(schars);
    String sortedt=new String(tchars);
    return sorteds.equals(sortedt);
}
           

//（2）哈希表
public boolean isAnagram(String s, String t) {
    int sLen=s.length();
    int tLen=t.length();
    if (sLen!=tLen) {
        return false;
    }
    //0:a  1:b  2:c...  依此类推
    //map[i]=j:s中i对应的字符的个数为j
    int[] map = new int[26];
    for(int i=0;i<sLen; i++) {
        map[s.charAt(i)-'a']++;
    }
    for(int i=0;i<tLen;i++) {
        map[t.charAt(i)-'a']--;
        //map[t.charAt(i)-'a']<0:字符串t中的字符t.charAt(i)的个数大于s中的
        //所以t不是s的字母异位词，直接返回false即可
        if (map[t.charAt(i)-'a']<0) {
            return false;
        }
    }
    return true;
}