LeetCode-Go 题解205. Isomorphic Strings 同构字符串双向哈希映射详解【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 205 题「同构字符串Isomorphic Strings」展开以 LeetCode-Go 仓库中 leetcode/0205.Isomorphic-Strings 目录下的官方题解文档为核心骨架结合 Go 源码实现与单元测试进行纵深剖析。读完本文你将掌握同构字符串的数学定义与判定条件、双向哈希映射双 map的底层原理、边界情况处理策略以及它与第 290 题「Word Pattern单词规律」的异同对照并可直接复制仓库中的可运行 Go 代码与测试用例进行验证。题目与定义LeetCode 205 题的原题描述如下Given two strings s and t, determine if they are isomorphic.Two strings are isomorphic if the characters in s can be replaced to get t.All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.翻译成大白话就是给定两个字符串s和t判断它们是否同构。所谓同构指的是s中的字符可以通过一一替换的方式得到t——同一个字符的所有出现位置必须被替换成同一个目标字符并且替换顺序与字符出现顺序保持一致同时不能有两个不同的源字符映射到同一个目标字符但允许某个字符映射到它自身。三个官方示例原题文档给出了三个示例仓库题解文档 leetcode/0205.Isomorphic-Strings/README.md 将其完整保留输入输出说明s eggt addtruee → ag → d一一对应s foot barfalsef → b、o → a后第二个o无法再映射到rs papert titletruep → t、a → i、e → l、r → e一一对应原题还有一个附加说明NoteYou may assume both s and t have the same length.即可以假定两个字符串长度相等。不过仓库源码仍然对长度不一致的情况做了防御性处理这一点会在下文「边界情况」中展开。解题思路本质是双向映射题解文档的「题目大意」与「解题思路」两节明确指出这道题和第 290 题基本是一样的。第 290 题是模式匹配这道题的题意是字符串映射实质是一样的。这道题做法和第 290 题基本一致。也就是说判断同构的核心在于验证s与t之间是否存在一个双射bijection。要判定双射必须同时满足两个方向的约束正向源 → 目标s中同一字符的所有出现必须映射到t中同一个字符否则不成立如示例 2 的foo→bar反向目标 → 源t中的同一字符不能被s中两个不同的字符共同映射否则也不成立。关于反向约束为什么必不可少第 290 题的题解文档 leetcode/0290.Word-Pattern/README.md 给出了一个非常经典的例子并说明了动机为什么需要记录双向的关系呢因为 Example 4 中a 对应了 dog这个时候 b 如果再对应 dog 是错误的所以这里需要从 dog 查询它是否已经和某个模式匹配过了。所以需要双向的关系。把 290 题的pattern abba、str dog dog dog dog这个例子移植到 205 题上如果只维护正向映射a → d、b → d会被允许但此时s中两个不同的字符a、b映射到了t中同一个字符d这违反了「No two characters may map to the same character」的约束因此必须用第二个 map 记录反向关系来拦截这类非法映射。仓库源码级实现剖析完整代码仓库中的 Go 实现位于 leetcode/0205.Isomorphic-Strings/205. Isomorphic Strings.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 }逐段解读第一步数据预处理与快速失败strList : []byte(t) patternByte : []byte(s) if (s t ! ) || (len(patternByte) ! len(strList)) { return false }代码先把两个字符串转成[]byte方便按下标逐个访问字符。随后做了两类快速失败fast-fail检查长度不一致虽然题目 Note 保证两串等长但实现仍对len(patternByte) ! len(strList)做了防御。若长度不同s与t的字符不可能一一对应直接返回false空串特例s t ! 时返回false。注意s t 这一组合不在拦截范围内两个空串是合法同构会走到下面的循环循环体一次都不执行最终返回true这一点与测试用例{, } → true完全吻合。第二步初始化两个方向的映射表pMap : map[byte]byte{} sMap : map[byte]byte{}pMap记录「源字符 → 目标字符」的正向映射以s的字符为键sMap记录「目标字符 → 源字符」的反向映射以t的字符为键。第三步逐字符遍历并校验双射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 } } }这是整个算法的核心逻辑上可分为四种情况情形条件动作情况 A源字符b未出现过且目标字符t[index]也未被其他源字符占用建立双向映射继续情况 B源字符b未出现过但目标字符t[index]已被占用且占用它的不是b返回false两个源字符争抢同一目标字符情况 C源字符b已出现过且其既有映射恰好等于t[index]双向映射一致继续情况 D源字符b已出现过但既有映射不等于t[index]返回false同一源字符映射到不同目标值得注意的是情况 B 中的sMap[strList[index]] ! b判断在逻辑上必然成立因为sMap[strList[index]]已存在且不等于当前未登记过的b但代码保留该判断与第 290 题实现保持完全一致的对称结构便于两题对照阅读。与第 290 题实现的对照将 205 题的实现与 leetcode/0290.Word-Pattern/290. Word Pattern.go 的wordPattern并排对比可以直观看到两者几乎是同一个模板对比维度205. Isomorphic Strings290. Word Pattern键值类型map[byte]byte字符 ↔ 字符map[byte]string模式字符 ↔ 单词切分方式直接按字节下标取字符先strings.Split(str, )按空格切词算法骨架双 map 逐下标遍历 双向校验完全相同空值处理s t ! 返回 falsepattern 返回 false两题的核心思想一致区别仅在于 290 题需要先把目标串按空格拆成单词序列再以「模式字符 ↔ 单词」建立双向映射。读者若已掌握 205 题几乎可以零成本迁移到 290 题。复杂度分析设n为字符串s与t的长度两者等长时间复杂度O(n)。只需一次线性遍历每个字符在 map 上的查询与写入均为 O(1)Go map 平均复杂度空间复杂度O(k)。两个 map 最多各存放k个不同字符其中k为字符串中不同字符的数量。对于本题输入k至多不超过 256 种不同字节值可视为常数级 O(1) 辅助空间。这也是该题被归为「哈希表Hash Table」类别的原因用空间换时间在单次遍历内完成双射校验。测试用例与验证方法仓库为本题配套了完整的单元测试位于 leetcode/0205.Isomorphic-Strings/205. Isomorphic Strings_test.go共覆盖 6 组用例qs : []question205{ {para205{egg, add}, ans205{true}}, // 官方示例 1 {para205{foo, bar}, ans205{false}}, // 官方示例 2 {para205{paper, title}, ans205{true}}, // 官方示例 3 {para205{, }, ans205{true}}, // 两个空串同构 {para205{ab, aa}, ans205{false}}, // b 与 a 争抢目标字符 a {para205{ab, a}, ans205{false}}, // 长度不一致 }这 6 个用例覆盖了三种关键场景正好与上文剖析的代码分支一一对应正例3 个egg/add、paper/title验证正常双射路径情况 A/C/验证空串特例走完空循环返回true反向冲突反例ab/aa中a → a建立后b试图映射到已被a占用的a触发情况 B 返回false直接验证了「No two characters may map to the same character」这一约束长度不一致反例ab/a触发长度快速失败分支返回false。在本地运行测试仓库根目录下提供了聚合测试脚本 gotest.sh其内部执行的是go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...在仓库根目录执行该脚本或直接go test ./leetcode/...即可运行全部题目测试若只想跑本题可针对单个包执行go test -v ./leetcode/0205.Isomorphic-Strings/从测试文件结构看question205结构体把「参数para205」与「期望答案ans205」打包成表格驱动用例这也是 LeetCode-Go 仓库统一的测试组织风格便于批量回归与覆盖率统计。边界情况汇总综合源码与测试解题时必须处理的边界情况有以下几类边界情况输入示例结果处理位置两个空串vstrue空循环自然结束仅一个为空串vsafalse快速失败分支长度不等abvsafalse快速失败分支目标字符被多个源字符争抢abvsaafalse情况 B反向 map 拦截源字符映射到多个目标foovsbarfalse情况 D正向 map 拦截字符映射到自身abcvsabctrue情况 A/C题目允许自映射小结第 205 题同构字符串是一道经典的哈希表应用题核心结论可以浓缩为三点判定标准是双射既要求「同一源字符只能映射到同一目标字符」又要求「同一目标字符只能被一个源字符映射」缺一不可双 map 是标准解法一个正向 map源 → 目标加一个反向 map目标 → 源单次 O(n) 遍历即可完成全部校验空间为 O(k)与 290 题同源本仓库题解明确将两题归为一类——把 205 题的目标串按空格切分后就演变为 290 题两题的 Go 实现采用完全相同的骨架可对照阅读 leetcode/0290.Word-Pattern/README.md 加深理解。如需动手验证可直接阅读并运行 leetcode/0205.Isomorphic-Strings 目录下的实现与测试或通过仓库根目录的 gotest.sh 执行全量测试。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Go 题解：205. Isomorphic Strings 同构字符串双向哈希映射详解
LeetCode-Go 题解205. Isomorphic Strings 同构字符串双向哈希映射详解【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 205 题「同构字符串Isomorphic Strings」展开以 LeetCode-Go 仓库中 leetcode/0205.Isomorphic-Strings 目录下的官方题解文档为核心骨架结合 Go 源码实现与单元测试进行纵深剖析。读完本文你将掌握同构字符串的数学定义与判定条件、双向哈希映射双 map的底层原理、边界情况处理策略以及它与第 290 题「Word Pattern单词规律」的异同对照并可直接复制仓库中的可运行 Go 代码与测试用例进行验证。题目与定义LeetCode 205 题的原题描述如下Given two strings s and t, determine if they are isomorphic.Two strings are isomorphic if the characters in s can be replaced to get t.All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.翻译成大白话就是给定两个字符串s和t判断它们是否同构。所谓同构指的是s中的字符可以通过一一替换的方式得到t——同一个字符的所有出现位置必须被替换成同一个目标字符并且替换顺序与字符出现顺序保持一致同时不能有两个不同的源字符映射到同一个目标字符但允许某个字符映射到它自身。三个官方示例原题文档给出了三个示例仓库题解文档 leetcode/0205.Isomorphic-Strings/README.md 将其完整保留输入输出说明s eggt addtruee → ag → d一一对应s foot barfalsef → b、o → a后第二个o无法再映射到rs papert titletruep → t、a → i、e → l、r → e一一对应原题还有一个附加说明NoteYou may assume both s and t have the same length.即可以假定两个字符串长度相等。不过仓库源码仍然对长度不一致的情况做了防御性处理这一点会在下文「边界情况」中展开。解题思路本质是双向映射题解文档的「题目大意」与「解题思路」两节明确指出这道题和第 290 题基本是一样的。第 290 题是模式匹配这道题的题意是字符串映射实质是一样的。这道题做法和第 290 题基本一致。也就是说判断同构的核心在于验证s与t之间是否存在一个双射bijection。要判定双射必须同时满足两个方向的约束正向源 → 目标s中同一字符的所有出现必须映射到t中同一个字符否则不成立如示例 2 的foo→bar反向目标 → 源t中的同一字符不能被s中两个不同的字符共同映射否则也不成立。关于反向约束为什么必不可少第 290 题的题解文档 leetcode/0290.Word-Pattern/README.md 给出了一个非常经典的例子并说明了动机为什么需要记录双向的关系呢因为 Example 4 中a 对应了 dog这个时候 b 如果再对应 dog 是错误的所以这里需要从 dog 查询它是否已经和某个模式匹配过了。所以需要双向的关系。把 290 题的pattern abba、str dog dog dog dog这个例子移植到 205 题上如果只维护正向映射a → d、b → d会被允许但此时s中两个不同的字符a、b映射到了t中同一个字符d这违反了「No two characters may map to the same character」的约束因此必须用第二个 map 记录反向关系来拦截这类非法映射。仓库源码级实现剖析完整代码仓库中的 Go 实现位于 leetcode/0205.Isomorphic-Strings/205. Isomorphic Strings.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 }逐段解读第一步数据预处理与快速失败strList : []byte(t) patternByte : []byte(s) if (s t ! ) || (len(patternByte) ! len(strList)) { return false }代码先把两个字符串转成[]byte方便按下标逐个访问字符。随后做了两类快速失败fast-fail检查长度不一致虽然题目 Note 保证两串等长但实现仍对len(patternByte) ! len(strList)做了防御。若长度不同s与t的字符不可能一一对应直接返回false空串特例s t ! 时返回false。注意s t 这一组合不在拦截范围内两个空串是合法同构会走到下面的循环循环体一次都不执行最终返回true这一点与测试用例{, } → true完全吻合。第二步初始化两个方向的映射表pMap : map[byte]byte{} sMap : map[byte]byte{}pMap记录「源字符 → 目标字符」的正向映射以s的字符为键sMap记录「目标字符 → 源字符」的反向映射以t的字符为键。第三步逐字符遍历并校验双射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 } } }这是整个算法的核心逻辑上可分为四种情况情形条件动作情况 A源字符b未出现过且目标字符t[index]也未被其他源字符占用建立双向映射继续情况 B源字符b未出现过但目标字符t[index]已被占用且占用它的不是b返回false两个源字符争抢同一目标字符情况 C源字符b已出现过且其既有映射恰好等于t[index]双向映射一致继续情况 D源字符b已出现过但既有映射不等于t[index]返回false同一源字符映射到不同目标值得注意的是情况 B 中的sMap[strList[index]] ! b判断在逻辑上必然成立因为sMap[strList[index]]已存在且不等于当前未登记过的b但代码保留该判断与第 290 题实现保持完全一致的对称结构便于两题对照阅读。与第 290 题实现的对照将 205 题的实现与 leetcode/0290.Word-Pattern/290. Word Pattern.go 的wordPattern并排对比可以直观看到两者几乎是同一个模板对比维度205. Isomorphic Strings290. Word Pattern键值类型map[byte]byte字符 ↔ 字符map[byte]string模式字符 ↔ 单词切分方式直接按字节下标取字符先strings.Split(str, )按空格切词算法骨架双 map 逐下标遍历 双向校验完全相同空值处理s t ! 返回 falsepattern 返回 false两题的核心思想一致区别仅在于 290 题需要先把目标串按空格拆成单词序列再以「模式字符 ↔ 单词」建立双向映射。读者若已掌握 205 题几乎可以零成本迁移到 290 题。复杂度分析设n为字符串s与t的长度两者等长时间复杂度O(n)。只需一次线性遍历每个字符在 map 上的查询与写入均为 O(1)Go map 平均复杂度空间复杂度O(k)。两个 map 最多各存放k个不同字符其中k为字符串中不同字符的数量。对于本题输入k至多不超过 256 种不同字节值可视为常数级 O(1) 辅助空间。这也是该题被归为「哈希表Hash Table」类别的原因用空间换时间在单次遍历内完成双射校验。测试用例与验证方法仓库为本题配套了完整的单元测试位于 leetcode/0205.Isomorphic-Strings/205. Isomorphic Strings_test.go共覆盖 6 组用例qs : []question205{ {para205{egg, add}, ans205{true}}, // 官方示例 1 {para205{foo, bar}, ans205{false}}, // 官方示例 2 {para205{paper, title}, ans205{true}}, // 官方示例 3 {para205{, }, ans205{true}}, // 两个空串同构 {para205{ab, aa}, ans205{false}}, // b 与 a 争抢目标字符 a {para205{ab, a}, ans205{false}}, // 长度不一致 }这 6 个用例覆盖了三种关键场景正好与上文剖析的代码分支一一对应正例3 个egg/add、paper/title验证正常双射路径情况 A/C/验证空串特例走完空循环返回true反向冲突反例ab/aa中a → a建立后b试图映射到已被a占用的a触发情况 B 返回false直接验证了「No two characters may map to the same character」这一约束长度不一致反例ab/a触发长度快速失败分支返回false。在本地运行测试仓库根目录下提供了聚合测试脚本 gotest.sh其内部执行的是go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...在仓库根目录执行该脚本或直接go test ./leetcode/...即可运行全部题目测试若只想跑本题可针对单个包执行go test -v ./leetcode/0205.Isomorphic-Strings/从测试文件结构看question205结构体把「参数para205」与「期望答案ans205」打包成表格驱动用例这也是 LeetCode-Go 仓库统一的测试组织风格便于批量回归与覆盖率统计。边界情况汇总综合源码与测试解题时必须处理的边界情况有以下几类边界情况输入示例结果处理位置两个空串vstrue空循环自然结束仅一个为空串vsafalse快速失败分支长度不等abvsafalse快速失败分支目标字符被多个源字符争抢abvsaafalse情况 B反向 map 拦截源字符映射到多个目标foovsbarfalse情况 D正向 map 拦截字符映射到自身abcvsabctrue情况 A/C题目允许自映射小结第 205 题同构字符串是一道经典的哈希表应用题核心结论可以浓缩为三点判定标准是双射既要求「同一源字符只能映射到同一目标字符」又要求「同一目标字符只能被一个源字符映射」缺一不可双 map 是标准解法一个正向 map源 → 目标加一个反向 map目标 → 源单次 O(n) 遍历即可完成全部校验空间为 O(k)与 290 题同源本仓库题解明确将两题归为一类——把 205 题的目标串按空格切分后就演变为 290 题两题的 Go 实现采用完全相同的骨架可对照阅读 leetcode/0290.Word-Pattern/README.md 加深理解。如需动手验证可直接阅读并运行 leetcode/0205.Isomorphic-Strings 目录下的实现与测试或通过仓库根目录的 gotest.sh 执行全量测试。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考