哈希算法题目：同构字符串

题目描述：
给定两个字符串 s 和 t，判断它们是否是同构的。如果 s 中的字符可以按某种映射关系替换得到 t，那么这两个字符串是同构的。每个出现的字符都应当映射到另一个字符，且不同字符不能映射到同一个字符。相同字符只能映射到同一个字符，字符可以映射到自己本身。

示例：
输入：s = "egg", t = "add"
输出：true
解释：e -> a, g -> d 的映射可以使得 s 变为 t。

输入：s = "foo", t = "bar"
输出：false
解释：o 无法同时映射到 a 和 r。

解题过程循序渐进讲解：

1. 理解“同构”的核心约束

   • 映射是双向的、一一对应的。
   • 从 s 到 t 的映射：s 中的每个字符都唯一映射到 t 的一个字符。
   • 从 t 到 s 的映射：t 中的每个字符也必须唯一映射回 s 的一个字符（避免多对一）。
   • 例子：s="ab", t="aa" 是 false，因为 a→a, b→a 导致 t 中的 a 被两个不同字符映射。

2. 选择数据结构：哈希表（字典）

   • 需要记录两边的映射关系。
   • 用两个哈希表：
     • map_s_to_t: 记录 s 中字符到 t 中字符的映射。
     • map_t_to_s: 记录 t 中字符到 s 中字符的映射。
   • 这样可同时检查：s 中字符是否映射一致，t 中字符是否被重复映射。

3. 逐步比较两个字符串

   • 遍历字符串，每次取 s[i] 和 t[i]。
   • 检查 map_s_to_t：
     • 如果 s[i] 已有映射，但映射值不等于 t[i] → 返回 false。
   • 检查 map_t_to_s：
     • 如果 t[i] 已有映射，但映射值不等于 s[i] → 返回 false。
   • 如果都通过，则将当前映射加入两个哈希表。

4. 详细推演示例

   • 例1：s="egg", t="add"

     • i=0: s[0]=e, t[0]=a
       两个哈希表都空，记录 map_s_to_t[e]=a, map_t_to_s[a]=e
     • i=1: s[1]=g, t[1]=d
       检查：g 未映射，d 未映射 → 记录 map_s_to_t[g]=d, map_t_to_s[d]=g
     • i=2: s[2]=g, t[2]=d
       检查：map_s_to_t[g] 存在且为 d，等于 t[2]（通过）
       map_t_to_s[d] 存在且为 g，等于 s[2]（通过）
     • 结束，返回 true

   • 例2：s="foo", t="bar"

     • i=0: s[0]=f, t[0]=b → 记录 f→b, b→f
     • i=1: s[1]=o, t[1]=a → 记录 o→a, a→o
     • i=2: s[2]=o, t[2]=r
       检查：map_s_to_t[o] 存在且为 a，但 a ≠ r → 返回 false

5. 边界情况与注意事项

   • 字符串长度必须相等，否则直接 false。
   • 字符包括所有 ASCII 可打印字符，但用哈希表可处理任意字符。
   • 时间复杂度 O(n)，空间复杂度 O(字符集大小)，这里最多是常数（ASCII 范围）。

6. 代码实现思路（伪代码）

   如果 s 长度 != t 长度: 返回 false
   初始化 map_s_to_t, map_t_to_s
   循环 i 从 0 到 n-1:
      字符 ch_s = s[i], ch_t = t[i]
      如果 map_s_to_t 包含 ch_s 且 map_s_to_t[ch_s] != ch_t: 返回 false
      如果 map_t_to_s 包含 ch_t 且 map_t_to_s[ch_t] != ch_s: 返回 false
      设置 map_s_to_t[ch_s] = ch_t
      设置 map_t_to_s[ch_t] = ch_s
   循环结束
   返回 true
   

7. 另一种思路：利用字符首次出现的位置

   • 同构意味着两个字符串中，每个位置上的字符在本字符串中首次出现的位置必须相同。
   • 例如 "egg" 中 e 首次出现位置0，g 首次出现位置1；"add" 中 a 首次出现位置0，d 首次出现位置1，所以匹配。
   • 实现时可用两个数组记录每个字符最近出现的位置，比较当前位置字符的上次出现位置是否一致。

这个题目巧妙利用哈希表维护双向映射，是哈希表检查一一对应关系的经典应用。