C++实现LeetCode(205.同构字符串)

前言LeetCode 205 要求判断两个字符串是否同构(isomorphic)。定义是:字符串s中的每个字符都能被替换成t中对应位置的字符,替换必须保持一致,且不同字符不能映射到同一个字符;反过来,t中的不同字符也不能由s中的同一个字符映射而来。换句话说,两个字符串的字符之间要存在一个双射(bijection)。题目保证两个字符串长度相同,但工程实现里仍然值得自己再校验一次。这道题的经典错误是只建立单向映射。例如s badc、t baba,只检查s到t,会看到b→b、a→a、d→b、c→a,每个s字符都只有一个映射,检查通过;但t中的b同时来自s的b和d,t中的a同时来自a和c,这不满足双射。因此必须同时维护s→t与t→s两张映射表,任何一张出现冲突都返回假。另一个常见误解是把「同构」理解成「两个字符串的字符出现次数分布相同」。ab与aa的计数分布不同,确实不同构;但ab与cc的计数分布相同(都是 1 和 1),它们不同构,因为两个不同的s字符不能映射到同一个t字符。所以计数法在这里是错的,必须检查映射关系。本文给出三种实现:双哈希表、定长数组、首次出现位置比较;分析各自的时间与空间复杂度,并说明 ASCII 前提与 Unicode 输入下的限制。示例以 C17 为基准。一、双映射的判定逻辑设两个字符串长度为n。对每个位置i,记a s[i]、b t[i]。维护s2t与t2s两张表。若a尚未出现在s2t中,写入s2t[a] b;否则检查s2t[a] b,不等则冲突。对t2s做对称的处理。只有两张表在所有位置都不冲突,才返回真。为什么两张表缺一不可?单看s→t,约束的是「同一个s字符必须始终映射到同一个t字符」;单看t→s,约束的是「同一个t字符必须始终来自同一个s字符」。前者排除foo与bar(第二个o要求映射到a,与第一次的b冲突),后者排除badc与baba。两个方向合起来才是双射。n为 0 或 1 时,循环不执行或只执行一次,自然返回真,不需要特判。二、哈希表实现用std::unordered_mapchar, char存两张表,查找与插入的均摊复杂度是 O(1),总时间 O(n),空间 O(min(n, 字符集大小))。实现时要用find查询,绝不能用operator[]:后者在键不存在时会插入一个值初始化的条目,既污染表,又让「是否存在」无法判断。元素插入用emplace,它返回pairiterator, bool,第二个成员表示是否真的插入了。这里不需要这个返回值,直接调用即可。三、定长数组实现LeetCode 的输入限定为可打印 ASCII,字符范围有限,可以用两个长度 256 的数组代替哈希表。数组里存「映射到的字符」,并用一个额外的布尔数组或特殊值表示「尚未映射」。更简洁的做法是把数组初始化为 -1,表示未映射;映射后用字符的整数值填充。用数组时有一个必须注意的细节:char是否有符号由实现定义。若char是有符号的,取值为 128 到 255 的字节会被解释成负数,直接拿来当下标就是越界访问,属于未定义行为(undefined behavior, UB)。正确做法是先static_castunsigned char再转std::size_t。数组版的时间仍是 O(n),空间固定为常数,常数因子比哈希表小,适合字符集固定的场景。但它把「只支持单字节字符集」这个前提写死了,遇到 UTF-8 多字节字符就会出错,接口上应当注明。四、首次出现位置法还有一个很短的写法:对每个位置i,检查s.find(s[i])是否等于t.find(t[i])。原理是,两个字符串同构当且仅当「每个字符首次出现的位置」在两个串中一一对应。因为首次出现位置编码了字符的出现次序与重复模式,模式相同就是同构。这个写法代码最短,但std::string::find每次从头扫描,最坏情况下每个位置都要扫一遍,总复杂度 O(n²)。字符串很长时不如前两种方法。它适合作为快速验证或面试时口述的思路,不适合放进性能敏感的代码。五、完整示例下面的示例实现三种方法,并在main中覆盖题目示例与几个边界用例。// 适用于 C17#include array#include iostream#include string#include unordered_map// 方法一:双哈希表,支持任意字符集(以 char 为单位)bool isIsomorphicMap(const std::string s, const std::string t) {if (s.size() ! t.size()) {return false;}std::unordered_mapchar, char s2t;std::unordered_mapchar, char t2s;for (std::size_t i 0; i s.size(); i) {const char a s[i];const char b t[i];const auto it s2t.find(a);if (it s2t.end()) {s2t.emplace(a, b);} else if (it-second ! b) {return false;}const auto jt t2s.find(b);if (jt t2s.end()) {t2s.emplace(b, a);} else if (jt-second ! a) {return false;}}return true;}// 方法二:定长数组,仅适用于单字节字符集bool isIsomorphicAscii(const std::string s, const std::string t) {if (s.size() ! t.size()) {return false;}std::arrayint, 256 s2t{};std::arrayint, 256 t2s{};s2t.fill(-1);t2s.fill(-1);for (std::size_t i 0; i s.size(); i) {const auto a static_castunsigned char(s[i]);const auto b static_castunsigned char(t[i]);if (s2t[a] -1) {s2t[a] static_castint(b);} else if (s2t[a] ! static_castint(b)) {return false;}if (t2s[b] -1) {t2s[b] static_castint(a);} else if (t2s[b] ! static_castint(a)) {return false;}}return true;}// 方法三:首次出现位置比较,代码最短但最坏 O(n^2)bool isIsomorphicFind(const std::string s, const std::string t) {if (s.size() ! t.size()) {return false;}for (std::size_t i 0; i s.size(); i) {if (s.find(s[i]) ! t.find(t[i])) {return false;}}return true;}int main() {struct Case {std::string s;std::string t;bool expected;};const Case cases[] {{egg, add, true},{foo, bar, false},{paper, title, true},{badc, baba, false},{ab, aa, false},{, , true},{a, z, true},};for (const Case c : cases) {const bool r1 isIsomorphicMap(c.s, c.t);const bool r2 isIsomorphicAscii(c.s, c.t);const bool r3 isIsomorphicFind(c.s, c.t);std::cout c.s / c.t - std::boolalpha r1 r2 r3 (expected c.expected )\n;}return 0;}按标准语义推演:egg与add中e→a、g→d,两张表都一致,返回真;foo与bar中第一个o→a,第二个o→r冲突,返回假;paper与title的映射为p→t、a→i、e→l、r→e,双向一致;badc与baba在t2s上冲突;ab与aa在t2s上冲突。三份实现对这些用例应当给出一致结果。以上只按代码逻辑推导,未经编译运行核对。常见坑点一、只维护一个方向的映射❌ 只建s2t,把badc与baba判成同构。✅ 同时维护s2t与t2s,任一方向冲突都返回假。二、用operator[]查询映射表❌if (s2t[a] 0) s2t[a] b;——键不存在时operator[]会插入默认值,既改表又让「是否映射过」失真。✅ 用find比较end(),插入用emplace。三、忘记检查长度❌ 直接按s.size()循环并访问t[i],长度不等时越界,std::string::operator[]越界是 UB。✅ 入口处if (s.size() ! t.size()) return false;。四、用计数分布判断同构❌ 统计两个串的字符频次,频次分布相同就返回真,ab与cc会被误判。✅ 同构要求存在双射,必须检查映射关系,而不是频次。五、char下标未转无符号❌s2t[s[i]]在char有符号且字节值大于 127 时下标为负,越界访问。✅ 用static_castunsigned char(s[i])再作为下标;数组大小取 256。六、认为空串或单字符需要特判❌ 额外加if (s.empty()) return true;的分支,逻辑重复且容易与长度检查冲突。✅ 循环本身就能正确处理n 0与n 1,只保留长度相等检查即可。七、用find法处理超长字符串❌ 每个位置都从头find,最坏 O(n²),长输入下明显变慢。✅ 用双哈希表或定长数组,时间 O(n);find法只作演示。八、把方法二用于 UTF-8 文本❌ 认为按字节比较等价于按字符比较,多字节字符被拆成多个「字符」参与映射。✅ 方法二的前提是单字节字符集;处理 Unicode 时应先解码成码点序列,再用哈希表按码点比较。总结方法时间复杂度空间复杂度字符集前提适用场景双哈希表O(n) 均摊O(min(n, σ))无(以char为单位)通用实现定长数组O(n)O(256)单字节字符集ASCII、追求常数首次出现位置O(n²) 最坏O(1) 额外无演示、短字符串判断同构的关键不是「字符出现次数」,而是「两个方向上的映射是否都一致」。实现时把长度检查、双向映射、以及数组下标的无符号转换这三处写对,这道题就没有别的陷阱了。若输入可能包含多字节字符,先明确字符集与解码方式,再套用同样的双映射逻辑。