242. 有效的字母异位词

🟢   🔖  哈希表 字符串 排序  🔗 力扣 LeetCode

题目

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 * 10^4
• 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 互为字母异位词。

解题思路

思路一：哈希表

异位词这类问题的关键在于，如何迅速判断两个字符串是异位词，主要考察数据编码和哈希表的使用。

可以使用哈希表，扫描字符串 s ，把 s 中的每个字符出现的次数存在哈希表中，再扫字符串 t，每出现一个字母就把哈希表中对应的字符减一，异位词中字符出现的次数肯定都是一样的，最终判断表中是否全部为 0 即可，有非 0 的数就输出 false 。

复杂度分析

• 时间复杂度: O(n)，其中 n 是字符串的长度，需要循环 n 次。
• 空间复杂度: O(k)，其中 k 是字符串 s 中不同的字符数量，使用哈希表存储不同字符的出现频率。

---

思路二：编码+哈希表

可以尝试找到一种编码方法，使得字母异位词的编码相同，找到这种编码方式之后，就可以用一个哈希表存储编码相同的所有异位词，得到最终的答案。

对字符串排序可以是一种编码方案，如果是异位词，排序后就变成一样的了，但是这样时间复杂度略高，且会修改原始数据。

更好的编码方案是利用每个字符的出现次数进行编码，也就是下面的解法代码。

复杂度分析

• 时间复杂度: O(n)，其中 n 是字符串的长度，需要循环 n 次。
• 空间复杂度: O(26)，使用了一个长度为 26 的辅助数组。

代码

哈希表

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function (s, t) {
	let map = new Map();
	for (let i of s) {
		let val = map.get(i) || 0;
		map.set(i, val + 1);
	}
	for (let j of t) {
		let val = map.get(j) || 0;
		map.set(j, val - 1);
	}
	return [...map.values()].filter((i) => i != 0).length === 0;
};

编码+哈希表

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function (s, t) {
	return encode(s) === encode(t);
};

var encode = function (str) {
	let res = new Array(26).fill(0);
	for (let i of str) {
		let code = i.charCodeAt() - 'a'.charCodeAt();
		res[code]++;
	}
	return res.join('_');
};

相关题目

题号	标题	题解	标签	难度
49	字母异位词分组	[✓]	数组 哈希表 字符串 1+
266	回文排列 🔒		位运算 哈希表 字符串
438	找到字符串中所有字母异位词	[✓]	哈希表 字符串 滑动窗口
2273	移除字母异位词后的结果数组		数组 哈希表 字符串 1+