LeetCode-Go 题解205. Isomorphic Strings同构字符串双哈希映射原理与 Go 实现【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇基于 LeetCode-Go 仓库对 LeetCode 205 题 Isomorphic Strings 的官方题解文档与源码深入讲解同构字符串的判定条件、双哈希映射的核心思路并结合仓库内的 Go 实现逐行拆解与测试用例验证。读完本文你将掌握如何用双向映射在 O(n) 时间内判断两字符串是否同构并理解它与 290. Word Pattern 模式匹配题在本质上的相通之处。题目描述给定两个字符串s和t判断它们是否是同构字符串isomorphic。如果s中的字符可以替换得到t那么这两个字符串是同构的。所有出现的字符都必须用另一个字符替换同时保留字符的顺序。两个字符不能映射到同一个字符但一个字符可以映射到它自身。题目原文与三个示例完整记录于 英文题解文档 与 中文题解文档。三个经典示例示例 1 Input: s egg, t add Output: true 示例 2 Input: s foo, t bar Output: false 示例 3 Input: s paper, t title Output: true题目的 Note 说明可以假设s和t长度相同仓库实现依然对长度不一致的情况做了防御性校验。同构的三条核心约束要正确理解同构字符串必须同时满足以下三个条件单射性正向映射唯一s中同一个字符必须始终映射到t中同一个字符。例如s egg字符g在索引 1 和 2 处出现两次必须都映射为t中的同一个字符。满射性反向映射唯一即无碰撞t中同一个字符只能被s中的一个字符映射。也就是说两个字符不能映射到同一个字符——例如s ab、t aa就不允许因为a和b都映射到了a。保序性替换必须保留字符顺序逐位置一一对应。正因如此只用一张正向映射表是不够的。示例 2 中s foo、t bar如果只看正向映射f - b、o - a、o - r会发现o同时映射到a和r正向表就能判定失败但s ab、t aa这种反向碰撞场景正向映射a - a、b - a各自唯一单表检查会误判为通过。这就是仓库实现必须同时维护两张哈希表的根本原因。题目大意与 290 题 Word Pattern 的本质关联原文档明确指出这道题和第 290 题基本是一样的。第 290 题是模式匹配这道题的题意是字符串映射实质是一样的。290. Word Pattern判断pattern如abba与句子中的单词序列如dog cat cat dog是否模式一致即字符 → 单词的双向映射。205. Isomorphic Strings判断s能否通过字符映射变成t即字符 → 字符的双向映射。两者都是判断两个序列之间的映射是否是一一对应的双射bijection问题区别只在于映射的目标类型不同。对比 290 题的源码 与本题源码可以发现除数据类型map[byte]string与map[byte]byte与切分方式strings.Split(str, )与[]byte(t)外控制流结构完全一致——两题共用同一套双表互查模板。解题思路双哈希映射核心思路是同时建立并校验两张映射表pMap正向表记录s中每个字符 →t中对应位置字符 的映射sMap反向表记录t中每个字符 →s中对应位置字符 的映射。遍历s与t的每一对字符(b, tChar)时若b尚未出现在正向表中若tChar也尚未出现在反向表中登记双向映射否则说明tChar已经被别的s字符占用发生反向碰撞返回false。若b已存在于正向表中校验pMap[b]是否等于当前的tChar不等则正向映射冲突返回false。只有完整遍历结束、从未发生冲突才返回true。Go 实现逐行拆解仓库中的完整实现位于 205. Isomorphic Strings.go与题解文档 中文版 中给出的代码完全一致package leetcode func isIsomorphic(s string, t string) bool { strList : []byte(t) patternByte : []byte(s) if (s t ! ) || (len(patternByte) ! len(strList)) { return false } pMap : map[byte]byte{} sMap : map[byte]byte{} for index, b : range patternByte { if _, ok : pMap[b]; !ok { if _, ok sMap[strList[index]]; !ok { pMap[b] strList[index] sMap[strList[index]] b } else { if sMap[strList[index]] ! b { return false } } } else { if pMap[b] ! strList[index] { return false } } } return true }逐段说明字符串转字节切片[]byte(t)与[]byte(s)将两个字符串转为字节切片便于按下标逐位访问。题目默认s、t由 ASCII 字符构成题目约束场景因此按字节处理即可。长度与空串防御(s t ! ) || (len(patternByte) ! len(strList))直接返回false。虽然题目 Note 假设两串等长但该分支同时兜底了长度不一致与s为空而t非空的异常输入。两张映射表pMap以s的字符为键sMap以t的字符为键类型均为map[byte]byte。Go 的 map 在键不存在时返回零值因此必须通过ok判断键是否存在而不能直接比较取值。正向键不存在时的分支反向键也不存在 → 登记pMap[b] tChar与sMap[tChar] b完成一次双向映射反向键已存在但对应值不等于b→ 反向碰撞返回false覆盖sab, taa这类用例反向键已存在且对应值等于b→ 说明之前已经双向登记过继续循环。正向键已存在时的分支校验pMap[b] ! tChar不相等说明s中同一字符被映射到了不同目标字符返回false覆盖sfoo, tbar这类用例。测试用例验证仓库为本题提供了表驱动风格的单元测试 205. Isomorphic Strings_test.go覆盖了以下六组用例输入s输入t期望结果覆盖点eggaddtrue正向多对一合法映射foobarfalse正向映射冲突o映射到两个字符papertitletrue长度 5 的复杂合法映射true两个空串视为同构abaafalse反向碰撞两个字符映射到同一字符abafalse长度不一致防御分支其中ab → aa这一组正是单张正向表会误判、必须双表互查的关键反例也是 205 题与 290 题共用的测试思想。测试通过Test_Problem205驱动isIsomorphic运行时打印每组【input】与【output】与仓库整体每题一测试、覆盖率 100%的组织方式保持一致仓库根目录 coverage.txt 记录了全量覆盖结果gotest.sh 提供了批量测试脚本。复杂度分析时间复杂度O(n)其中 n 为字符串长度。单次线性遍历每次循环内对两张 map 的查询与写入均为 O(1)Go map 平均复杂度。空间复杂度O(k)k 为字符串中出现的不同字符数最坏情况下 O(n)。两张 map 各存储至多 n 个键值对。变体与扩展理解了双哈希映射模板后可以将其迁移到一系列判断双射关系的题目290. Word Pattern同样的双表结构映射目标从字符变为单词区别在于需要先用strings.Split按空格切分句子且正向表类型变为map[byte]string。字符 → 字符 与 模式 → 词 的统一抽象两者都可概括为给定两个序列 A、B判断是否存在一个双射 f使得 f(A[i]) B[i] 对所有位置 i 成立。判定关键永远在于正向唯一A 中同一元素只能对应一个 B 元素且反向唯一B 中同一元素只能被一个 A 元素对应。如果希望更深入地理解本仓库对字符串类题目的整体解法组织方式可参阅 Chapter Two / String 专题 与 Chapter Two / Hash_Table 专题。本题即属于典型的字符串 哈希表交叉考点。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考