天天看点

LeetCode_排序_中等_242.有效的字母异位词1.题目2.思路3.代码实现(Java)

目录

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