[LeetCode] 242. Valid Anagram

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:
Input: s = “anagram”, t = “nagaram”
Output: true

Example 2:
Input: s = “rat”, t = “car”
Output: false

Constraints:
1 <= s.length, t.length <= 5 * 104
s and t consist of lowercase English letters.

Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?

有效的字母异位词。

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

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/valid-anagram
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这题用 counting sort 做，会用到 hashmap。思路是建立一个 hashmap，先扫描 s，记录 s 里面每个字母出现的次数；然后遍历 t 的时候，减去 t 里面每个字符出现的次数，如果这个过程中发现 t 中有任何字符在 hashmap 里不存在，就 return false。若没有，则再次遍历 hashmap，如果有任何一个 key 的 value 不是 0，也 return false。

这道题我们注意题目问的 followup，如果字符串里也有其他字符怎么办？这里我们的处理办法是把 count 数组变成256位，然后对于每个遇到的字符 char，我们直接就对 count[s.charAt(i)] 做加或减的操作。再要不然就直接用 hashmap 即可。

复杂度

时间O(n)
空间O(n)

代码

Java实现

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

        // normal case
        int[] count = new int[256];
        for (int i = 0; i < s.length(); i++) {
            // count[s.charAt(i) - 'a']++;
            count[s.charAt(i)]++;
            count[t.charAt(i)]--;
        }
        for (int j = 0; j < count.length; j++) {
            if (count[j] != 0) {
                return false;
            }
        }
        return true;
    }
}

JavaScript实现

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
    let map = {};
    for (let i = 0; i < s.length; i++) {
        if (!map[s[i]]) {
            map[s[i]] = 1;
        } else {
            map[s[i]]++;
        }
    }
    for (let i = 0; i < t.length; i++) {
        if (!map[t[i]] || map[t[i]] < 0) {
            return false;
        } else {
            map[t[i]]--;
        }
    }
    for (let key in map) {
        if (map[key] !== 0) {
            return false;
        }
    }
    return true;
};