205. 同构字符串 - Java 解法与优化

205. 同构字符串

给定两个字符串 s 和 t，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

示例 1： 输入：s = "egg", t = "add" 输出：true 解释： 字符串 s 和 t 可以通过以下方式变得相同： 将 'e' 映射为 'a'。 将 'g' 映射为 'd'。

示例 2： 输入：s = "f11", t = "b23" 输出：false 解释： 字符串 s 和 t 无法变得相同，因为 '1' 需要同时映射到 '2' 和 '3'。

示例 3： 输入：s = "paper", t = "title" 输出：true

提示： 1 <= s.length <= 5 * 10^4 t.length == s.length s 和 t 由任意有效的 ASCII 字符组成

第一次解答

解题思路

核心方法：双向哈希表映射法，通过两个 HashMap 分别维护 s→t 和 t→s 的字符映射关系，确保'相同字符映射唯一'且'不同字符不映射到同一字符'，逻辑严谨且能完全满足题目约束，时间复杂度 O(n)、空间复杂度 O(k)（k 为不同字符数）。

核心逻辑拆解

判断同构字符串的核心是'双向唯一映射'：

1. 正向约束：s 中的同一个字符，必须始终映射到 t 中的同一个字符（比如 s 的'e'不能既映射到'a'又映射到'b'）；
2. 反向约束：t 中的同一个字符，只能被 s 中的一个字符映射（比如 s 的'e'和'g'不能同时映射到 t 的'a'）；
3. 用两个 HashMap 分别记录：
   • map：key 为 s 的字符，value 为 t 的字符（正向映射）；
   • map2：key 为 t 的字符，value 为 s 的字符（反向映射）；
4. 遍历每个字符位置 i：
   • 若 s[i] 已在 map 中，检查 map.get(s[i]) 是否等于 t[i]，不等则返回 false；
   • 若 s[i] 不在 map 中，检查 t[i] 是否已在 map2 中（避免不同 s 字符映射到同一 t 字符），若存在则返回 false；
   • 若都满足，将 s[i]→t[i] 存入 map，t[i]→s[i] 存入 map2；
5. 遍历完成后返回 true。

具体步骤（以示例 1 s="egg"，t="add"为例）

1. i=0（s='e'，t='a'）：
   • map无'e'，map2无'a' → 存入 map(e→a)、map2(a→e)；
2. i=1（s='g'，t='d'）：
   • map无'g'，map2无'd' → 存入 map(g→d)、map2(d→g)；
3. i=2（s='g'，t='d'）：
   • map有'g'，且 map.get(g)=d == t[i] → 验证通过；
4. 遍历完成，返回 true。

性能说明

• 时间复杂度：O(n)（仅遍历字符串一次，HashMap 的增删查操作均为 O(1)）；
• 空间复杂度：O(k)（k 为字符串中不同字符的数量，最多为 256 个 ASCII 字符）；
• 优势：逻辑直观，双向映射能完全覆盖题目所有约束（相同字符唯一映射、不同字符不重复映射）；
• 潜在优化点：HashMap 的自动装箱/拆箱、哈希计算有轻微开销，可通过数组优化进一步提升性能。

public   {
    Map<Character, Character> map =  <>();
    Map<Character, Character> map2 =  <>();
     (   ; i < s.length(); i++) {
           s.charAt(i);
         (map.containsKey(a)) {
             (!map.get(a).equals(t.charAt(i))) {
                 ;
            }
        }  {
             (map2.containsKey(t.charAt(i))) {
                 ;
            }  {
                map.put(a, t.charAt(i));
                map2.put(t.charAt(i), a);
            }
        }
    }
     ;
}