有效的字母异位词

怎样从“判断 t="nagaram" 是否能由 s="anagram" 重新排列得到(返回 true)。”推导出 哈希计数 · 抵消，并证明每次状态变化都不会漏掉答案？

中心结论：先比长度;再用长度 26 的计数表:扫 s 时每个字符 +1,扫 t 时每个字符 -1,中途出现负数立刻 false,否则全部归零返回 true。

给出 2 个字符串 s 和 t，如果 t 中的字母在 s 中都存在，输出 true，否则输出 false。

在本站主例中，判断 t="nagaram" 是否能由 s="anagram" 重新排列得到(返回 true)。

算法最终需要得到或观察：所有字符计数都归零,返回 true。

逐对枚举能够得到答案，但同一个查找会发生许多次；哈希表把已经见过的信息保存成一次查询。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“哈希记忆表”，明确答案需要观察什么。
2. 2状态只维护 字符计数表 count[26]、当前扫描阶段(s 或 t)。
3. 3转移每一步按照 先比长度;再用长度 26 的计数表:扫 s 时每个字符 +1,扫 t 时每个字符 -1,中途出现负数立刻 false,否则全部归零返回 true。
4. 4收尾读取 所有字符计数都归零,返回 true。，并复核边界与复杂度。

先问未来需要查询什么，再决定 map 的 key 与 value。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：字符计数表 count[26]、当前扫描阶段(s 或 t)。

这道题可以用打表的方式做。先把 s 中的每个字母都存在一个 26 个容量的数组里面，每个下标依次对应 26 个字母。s 中每个字母都对应表中一个字母，每出现一次就加 1。然后再扫字符串 t，每出现一个字母就在表里面减一。如果都出现了，最终表里面的值肯定都是 0 。最终判断表里面的值是否都是 0 即可，有非 0 的数都输出 false 。

先比长度;再用长度 26 的计数表:扫 s 时每个字符 +1,扫 t 时每个字符 -1,中途出现负数立刻 false,否则全部归零返回 true。

执行过程中持续维护：字符计数表 count[26]、当前扫描阶段(s 或 t)。

正确性依赖以下不变量：扫描过程中,count[x] = s 已提供的字母 x 数量 − t 已消耗的字母 x 数量;异位词最终应全部归零。

面试时可以压缩为：先判断 len(s) 与 len(t) 是否相等,不等直接 false;因为只含小写英文字母,用长度 26 的数组记录字符频率:遍历 s 每个字符计数 +1,遍历 t 每个字符计数 -1,过程中出现负数立刻 false,全部扫完无负数返回 true。时间 O(n),空间 O(1)。

落到当前题，执行机制可以压缩为：先比长度;再用长度 26 的计数表:扫 s 时每个字符 +1,扫 t 时每个字符 -1,中途出现负数立刻 false,否则全部归零返回 true。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入判断 t="nagaram" 是否能由 s="anagram" 重新排列得到(返回 true)。 因为：先比长度;再用长度 26 的计数表:扫 s 时每个字符 +1,扫 t 时每个字符 -1,中途出现负数立刻 false,否则全部归零返回 true。
2. 2统计 s:'n' 计数 +1s 的字符 'n' 出现一次,对应计数 +1。 因为：s 贡献正数,稍后 t 贡献负数,异位词应当全部抵消为 0。
3. 3预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
4. 4统计 s:'a' 计数 +1s 的字符 'a' 出现一次,对应计数 +1。 因为：s 贡献正数,稍后 t 贡献负数,异位词应当全部抵消为 0。
5. 5核对 t:'n' 计数 -1t 的字符 'n' 抵消一次计数。 因为：若是异位词,t 的每个字符都能在 s 的计数里找到抵消。
6. 6核对 t:'a' 计数 -1t 的字符 'a' 抵消一次计数。 因为：若是异位词,t 的每个字符都能在 s 的计数里找到抵消。
7. 7核对 t:'a' 计数 -1t 的字符 'a' 抵消一次计数。 因为：若是异位词,t 的每个字符都能在 s 的计数里找到抵消。
8. 8收尾与复杂度所有字符计数都归零,返回 true。 因为：时间 O(n) · 空间 O(1)。先比长度;再用长度 26 的计数表:扫 s 时每个字符 +1,扫 t 时每个字符 -1,中途出现负数立刻 false,否则全部归零返回 true。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// 解法一
func isAnagram(s string, t string) bool {
	alphabet := make([]int, 26)
	sBytes := []byte(s)
	tBytes := []byte(t)
	if len(sBytes) != len(tBytes) {
		return false
	}
	for i := 0; i < len(sBytes); i++ {
		alphabet[sBytes[i]-'a']++
	}
	for i := 0; i < len(tBytes); i++ {
		alphabet[tBytes[i]-'a']--
	}
	for i := 0; i < 26; i++ {
		if alphabet[i] != 0 {
			return false
		}
	}
	return true
}

// 解法二
func isAnagram1(s string, t string) bool {
	hash := map[rune]int{}
	for _, value := range s {
		hash[value]++
	}
	for _, value := range t {
		hash[value]--
	}
	for _, value := range hash {
		if value != 0 {
			return false
		}
	}
	return true
}

func main() {
    // 1. 主例
    //    输入：mode="anagram", s="anagram", t="nagaram"
    //    期望：所有字符计数都归零,返回 true。
    //
    // 2. 失败 / 未命中
    //    检查：只检查 t 的字符够不够,漏掉 t 比 s 多字符(出现负计数)的情况。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC49 字母异位词分组；LC1 两数之和
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意判断 t="nagaram" 是否能由 s="anagram" 重新排列得到(返回 true)。
2. 2重复逐对枚举能够得到答案，但同一个查找会发生许多次；哈希表把已经见过的信息保存成一次查询。
3. 3优化先比长度;再用长度 26 的计数表:扫 s 时每个字符 +1,扫 t 时每个字符 -1,中途出现负数立刻 false,否则全部归零返回 true。
4. 4证明扫描过程中,count[x] = s 已提供的字母 x 数量 − t 已消耗的字母 x 数量;异位词最终应全部归零。
5. 5复杂度时间 O(n)，空间 O(1)