16. Check Valid Anagram

Origin: Check Valid Anagram

Given two strings s and t, return 1 if t is an anagram of s, otherwise return 0.

Example 1

Input: s = “listen” t = “silent”

Output: 1

Explanation: Build a frequency map for ‘listen’: {l:1, i:1, s:1, t:1, e:1, n:1}. Iterate over ‘silent’: all counts return to zero, so they are anagrams.

Example 2

Input: s = “hello” t = “bellow”

Output: 0

Explanation: Different lengths (5 vs 6), not anagrams.

Input Format

• Line 1: A string s of length n, where 0 <= n <= 1000, containing only lowercase letters ‘a’ to ‘z’.
• Line 2: A string t of length m, where 0 <= m <= 1000, containing only lowercase letters ‘a’ to ‘z’.
• Both strings may be empty.

Constraints

• 0 <= s.length <= 1000
• 0 <= t.length <= 1000
• Only lowercase letters ‘a’ to ‘z’

Output Format

• 1 if t is an anagram of s
• 0 otherwise

Sample Input 0

a
a

Sample Output 0

1

Sample Input 1

ab
ba

Sample Output 1

1

---

函数契约

// 输入：s（字符串），t（字符串）
// 输出：1 或 0（整数，不是布尔值）
// 边界：长度不同 → 0；都为空 → 1；单字符相同 → 1

边界表

场景	返回什么
长度不同	0
都为空	1
单字符相同	1
字符相同顺序不同	1
字符不同	0

Resolution

我的解法

function isAnagram(s: string, t: string): number {
    if (s.length !== t.length) return 0
    let sMap = new Map<string, number>();
    for (let i = 0; i < s.length; i++) {
        sMap.set(s[i], (sMap.get(s[i]) || 0) + 1);
    }
 
    for (let i = 0; i < t.length; i++) {
        if (sMap.has(t[i])) {
            sMap.set(t[i], sMap.get(t[i])! - 1)
        }
    }
 
    for (let value of sMap.values()) {
        if (value !== 0) return 0
    }
 
    return 1
}

解题思路

三步：长度检查 → 建频率表 → 遍历 t 减频率 → 检查全为 0。

1. 长度不同直接返回 0，这是最简单的边界判断
2. 对 s 建字符频率表，sMap.set(s[i], (sMap.get(s[i]) || 0) + 1) 累加计数
3. 遍历 t，每个字符在频率表里减 1
4. 最后检查频率表所有值是否为 0，有非 0 说明字符数量不匹配

可优化：提前退出

第三轮遍历可以省掉。遍历 t 减频率时，如果某个字符不在 sMap 里或减到负数，直接返回 0：

for (let i = 0; i < t.length; i++) {
    if (!sMap.has(t[i])) return 0
    const count = sMap.get(t[i])! - 1
    if (count < 0) return 0
    sMap.set(t[i], count)
}
return 1

区别在于：遇到 t 中字符不在 s 里，或 t 中某字符比 s 多，立刻返回 0，不用等遍历完再检查。多一轮遍历但不影响 O(n) 复杂度。

踩坑经历

第一版存的是索引 sMap.set(s[i], i) 而不是频率，只能判断”字符是否出现过”，不能判断”出现次数是否相同”。

复杂度

• 时间：O(n)，n 是字符串长度
• 空间：O(1)，字符只有 a-z 共 26 个，Map 最多 26 个 entry

参考来源

• 相关文章：算法解题流程：从读题到提交的七步
• 相关题目：15. Two Sum — 同样是哈希表思路，一个是查补数，一个是查频率