526互联

Leetcode 242. 有效的字母异位词(Valid anagram)

发布时间 2023-08-21 09:18:00作者: Ahci

题目链接?

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

思路

开始没看清题目就直接上手, 使用Set判断是否包含, 结果忽略了字符出现次数的问题, 收获了一个解答错误.

理清思路后发现可以使用HashMap, 将字符串s的每个字符设为key, 出现次数设为value, 之后使用字符串t将出现次数一一减去即可. 在设置value时需要注意的问题是如何为重复出现的字符增加次数, 这里使用了HashMap的getOrDefault()方法.

第二种方法是创建一个长度为26的int数组, 在字符串s对应字符出现处+1, 字符串t对应字符出现处-1, 若最后数组中有数值小于0则返回false.

上面两种方法都可以在代码的开头判断两字符串长度是否一致, 若不一致直接返回false.

代码实现

HashMap:

class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()) {
            return false;
        }
        HashMap<Character, Integer> map = new HashMap<>();
        char[] chars = s.toCharArray();
        
        for(char c : chars) {
            // 向map中存入一个键值对，key为c，若c已存在则+1，不存在则存入提供的默认值0
            map.put(c, map.getOrDefault(c, 0) + 1);  
        }

        chars = t.toCharArray();

        for(char c : chars) {
            map.put(c, map.getOrDefault(c, 0) - 1);
            if(map.get(c) < 0) {
                return false;
            }
        }

        return true;
    }
}

数组:

class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()) {
            return false;
        }

        int[] charCount = new int[26];

        for(int i = 0; i < s.length(); i++) {
            charCount[s.charAt(i) - 'a']++;
            charCount[t.charAt(i) - 'a']--;
        }

        for(int count : charCount) {
            if(count != 0) {
                return false;
            }
        }

        return true;
    }
}