当前位置：首页 > news >正文

49-有效的字母异位词

news 2025/6/27 7:43:23

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

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

提示:

1 <= s.length, t.length <= 5 * 104
s 和 t 仅包含小写字母

进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

方法一：排序比较法

将字符串转换为字符数组，排序后比较是否相同。

function isAnagram(s: string, t: string): boolean {if (s.length !== t.length) return false;// 将字符串转换为字符数组并排序const sSorted = s.split('').sort().join('');const tSorted = t.split('').sort().join('');return sSorted === tSorted;
}

方法二：哈希表统计法

使用哈希表统计每个字符的出现次数，比较两个哈希表是否相同。

function isAnagram(s: string, t: string): boolean {if (s.length !== t.length) return false;const mapS = new Map<string, number>();const mapT = new Map<string, number>();// 统计s中字符频率for (const char of s) {mapS.set(char, (mapS.get(char) || 0) + 1);}// 统计t中字符频率for (const char of t) {mapT.set(char, (mapT.get(char) || 0) + 1);}// 比较两个哈希表是否相同if (mapS.size !== mapT.size) return false;for (const [char, count] of mapS.entries()) {if (mapT.get(char)! !== count) {return false;}}return true;
}

方法三：数组计数法（针对小写字母优化）

使用固定大小的数组（26 个元素）统计每个字符的出现次数。

function isAnagram(s: string, t: string): boolean {if (s.length !== t.length) return false;const count = new Array(26).fill(0);// 统计s中字符频率（增加计数）for (const char of s) {count[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;}// 统计t中字符频率（减少计数）for (const char of t) {const index = char.charCodeAt(0) - 'a'.charCodeAt(0);count[index]--;// 如果某个字符计数小于0，说明t中该字符多于sif (count[index] < 0) {return false;}}return true;
}

方法四：Unicode 支持版本

使用哈希表统计字符频率，支持处理任意 Unicode 字符。

function isAnagram(s: string, t: string): boolean {if (s.length !== t.length) return false;const map = new Map<string, number>();// 统计s中所有Unicode字符的频率for (let i = 0; i < s.length; i++) {const char = s[i];// 处理代理对（surrogate pair）if (i < s.length - 1 && isSurrogatePair(s, i)) {const codePoint = getCodePoint(s, i);const str = String.fromCodePoint(codePoint);map.set(str, (map.get(str) || 0) + 1);i++; // 跳过代理对的第二个字符} else {map.set(char, (map.get(char) || 0) + 1);}}// 检查t中所有Unicode字符的频率for (let i = 0; i < t.length; i++) {const char = t[i];if (i < t.length - 1 && isSurrogatePair(t, i)) {const codePoint = getCodePoint(t, i);const str = String.fromCodePoint(codePoint);const count = map.get(str) || 0;if (count === 0) return false;map.set(str, count - 1);i++;} else {const count = map.get(char) || 0;if (count === 0) return false;map.set(char, count - 1);}}// 确保所有字符的计数都为0for (const count of map.values()) {if (count !== 0) return false;}return true;
}// 判断两个字符是否构成代理对
function isSurrogatePair(str: string, index: number): boolean {const code = str.charCodeAt(index);return code >= 0xD800 && code <= 0xDBFF && index + 1 < str.length && str.charCodeAt(index + 1) >= 0xDC00 && str.charCodeAt(index + 1) <= 0xDFFF;
}// 获取代理对的码点值
function getCodePoint(str: string, index: number): number {const high = str.charCodeAt(index);const low = str.charCodeAt(index + 1);return ((high - 0xD800) * 0x400) + (low - 0xDC00) + 0x10000;
}

复杂度分析

方法	时间复杂度	空间复杂度	适用范围
方法一（排序）	O(n log n)	O(n)	所有字符类型，依赖排序算法
方法二（哈希表）	O(n)	O(k)	所有字符类型，k 为不同字符的数量
方法三（数组）	O(n)	O(1)	仅适用于小写字母
方法四（Unicode）	O(n)	O(k)	所有 Unicode 字符，处理代理对

测试示例

// 示例1测试
console.log(isAnagram("anagram", "nagaram"));  // 输出: true// 示例2测试
console.log(isAnagram("rat", "car"));          // 输出: false// 测试大小写敏感
console.log(isAnagram("a", "A"));              // 输出: false// 测试Unicode字符
console.log(isAnagram("😀😁😂", "😂😁😀"));    // 输出: true
console.log(isAnagram("你好", "好你"));        // 输出: true