242. 有效的字母异位词
题目描述
输入两个字符串 s 和 t。
如果 t 只是把 s 的字母换了个顺序，也就是两者用到的每个字母及其个数都相同，就称 t 是 s 的字母异位词。
是字母异位词时返回 true，否则返回 false。
示例 1
输入：s = "anagram", t = "nagaram" 输出：true
解释：两个字符串都由 3 个 a、1 个 n、1 个 g、1 个 r、1 个 m 组成。
示例 2
输入：s = "rat", t = "car" 输出：false
解释：s 里有字母 t，t 里没有；t 里有字母 c，s 里没有。
数据范围
1 <= s.length, t.length <= 5 * 10^4s和t只由小写英文字母组成。
进阶：如果字符串中可能出现 Unicode 字符，你的做法要怎样调整？
解题思路：计数数组
长度不同直接返回 false。否则用长度 26 的计数数组：扫 s 时每个字母 +1，再扫 t 时每个字母 -1。一旦某个计数变成负数，说明 t 里这个字母比 s 多，返回 false。长度相同又没有负数，就说明所有计数恰好归 0。
为什么正确
扫过 t 的前 j 个字母后，cnt[c] = s 中 c 的个数 − t[:j] 中 c 的个数。
复杂度分析
时间 O(n)；空间 O(26)。
易错点
别忘了先比较长度：只检查“不出现负数”时，t 比 s 短（如 s="ab", t="a"）也会被误判为 true。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
cnt = [0] * 26
for ch in s:
cnt[ord(ch) - ord('a')] += 1
for ch in t:
cnt[ord(ch) - ord('a')] -= 1
if cnt[ord(ch) - ord('a')] < 0:
return False
return Trueclass Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
int[] cnt = new int[26];
for (char ch : s.toCharArray()) {
cnt[ch - 'a'] += 1;
}
for (char ch : t.toCharArray()) {
cnt[ch - 'a'] -= 1;
if (cnt[ch - 'a'] < 0) {
return false;
}
}
return true;
}
}class Solution {
public:
bool isAnagram(string s, string t) {
if (s.size() != t.size()) {
return false;
}
vector<int> cnt(26, 0);
for (char ch : s) {
cnt[ch - 'a'] += 1;
}
for (char ch : t) {
cnt[ch - 'a'] -= 1;
if (cnt[ch - 'a'] < 0) {
return false;
}
}
return true;
}
};func isAnagram(s string, t string) bool {
if len(s) != len(t) {
return false
}
cnt := make([]int, 26)
for i := 0; i < len(s); i++ {
cnt[s[i]-'a'] += 1
}
for i := 0; i < len(t); i++ {
cnt[t[i]-'a'] -= 1
if cnt[t[i]-'a'] < 0 {
return false
}
}
return true
}var isAnagram = function(s, t) {
if (s.length !== t.length) {
return false;
}
const cnt = new Array(26).fill(0);
for (const ch of s) {
cnt[ch.charCodeAt(0) - 97] += 1;
}
for (const ch of t) {
cnt[ch.charCodeAt(0) - 97] -= 1;
if (cnt[ch.charCodeAt(0) - 97] < 0) {
return false;
}
}
return true;
};function isAnagram(s: string, t: string): boolean {
if (s.length !== t.length) {
return false;
}
const cnt: number[] = new Array(26).fill(0);
for (const ch of s) {
cnt[ch.charCodeAt(0) - 97] += 1;
}
for (const ch of t) {
cnt[ch.charCodeAt(0) - 97] -= 1;
if (cnt[ch.charCodeAt(0) - 97] < 0) {
return false;
}
}
return true;
}其他解法
排序后比较最简洁，但要 O(n log n)；计数数组利用字符集只有 26 个小写字母，线性时间完成。
解法 2：排序后比较 时间 O(n log n)，空间 O(n)
两个字符串互为字母异位词，当且仅当把各自的字符排序后得到的字符串相同。分别排序后直接比较。
一两行就能写完，不依赖字符集大小，输入含 Unicode 字符时也能直接用。排序是 O(n log n)，比计数慢。
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
return sorted(s) == sorted(t)class Solution {
public boolean isAnagram(String s, String t) {
char[] a = s.toCharArray(), b = t.toCharArray();
Arrays.sort(a);
Arrays.sort(b);
return Arrays.equals(a, b);
}
}class Solution {
public:
bool isAnagram(string s, string t) {
sort(s.begin(), s.end());
sort(t.begin(), t.end());
return s == t;
}
};func isAnagram(s string, t string) bool {
a, b := []byte(s), []byte(t)
sort.Slice(a, func(i, j int) bool { return a[i] < a[j] })
sort.Slice(b, func(i, j int) bool { return b[i] < b[j] })
return string(a) == string(b)
}var isAnagram = function(s, t) {
return [...s].sort().join('') === [...t].sort().join('');
};function isAnagram(s: string, t: string): boolean {
return [...s].sort().join('') === [...t].sort().join('');
}