LC242
有效的字母异位词
哈希计数 · 抵消可视化:哈希表判断字符串 b="tar" 是否是 a="rat" 的字母重排。
时间 O(n)空间 O(1)
题目1 / 19
题目与输入建立输入、目标与算法心智
先比长度:|a|=7,|b|=7
正在加载算法场景...
当前发生了什么
判断字符串 b="tar" 是否是 a="rat" 的字母重排。
机器状态
字符计数表 count、当前扫描阶段(a 或 b)。
为什么正确
先比长度;再用计数表:扫 a 时每个字符 +1,扫 b 时每个字符 -1,异位词应让所有计数归零。
不变量
异位词 ⇔ 每个字符计数恰好抵消为 0。
面试怎么说
先比长度,不同直接 false;再用计数表,a 加 b 减,过程中出现负数立刻 false,最后全 0 即 true,O(n)、空间 O(1)(字符集固定)。
人类输入
判断字符串 b="tar" 是否是 a="rat" 的字母重排。
机制
先比长度;再用计数表:扫 a 时每个字符 +1,扫 b 时每个字符 -1,异位词应让所有计数归零。
机器状态
字符计数表 count、当前扫描阶段(a 或 b)。
可观察结果
所有字符计数都归零,返回 true。
不变量
- · 异位词 ⇔ 每个字符计数恰好抵消为 0。
常见误区
- · 只检查 b 的字符够不够,漏掉 b 比 a 多字符(出现负计数)的情况。
迁移练习
- · LC49 字母异位词分组
- · LC1 两数之和
面试怎么答
先比长度,不同直接 false;再用计数表,a 加 b 减,过程中出现负数立刻 false,最后全 0 即 true,O(n)、空间 O(1)(字符集固定)。