LC205. 同构字符串

题目描述

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

示例 1: 输入：s = "egg", t = "add" 输出：true 示例 2： 输入：s = "foo", t = "bar" 输出：false 示例 3： 输入：s = "paper", t = "title" 输出：true 提示： 1 <= s.length <= 5 * 10^4 t.length == s.length s 和 t 由任意有效的 ASCII 字符组成

题目解析

题目在说什么

我们有两个字符串，比如 s = "egg" 和 t = "add"。题目问：能不能把 s 里的每个字母，通过一种“一对一”的替换规则，变成 t？如果能，就说这两个字符串是“同构”的。

什么叫“一对一”的替换规则？就是：

• 每个在 s 中出现的字符，只能固定映射到 t 中的一个字符。比如 'e' 只能变成 'a'，不能有时候变成 'a' 有时候变成 'b'。
• 不同的字符不能映射到同一个字符。比如 'e' 和 'g' 不能都变成 'a'，因为那样 'a' 就不知道是谁变的了。
• 字符可以映射到自己，比如 'a' 变成 'a' 是允许的。

举个反例：s = "foo"，t = "bar"。'f' 变成 'b'，'o' 变成 'a'？但注意 s 里有两个 'o'，按照规则，它们必须变成同一个字符，可是 t 里对应位置是 'a' 和 'r'，不一样，所以不行。

思路是怎么来的

想象一下，你是一个翻译官，要把 s 里的每个字母翻译成 t 里的字母。你手里有两本“翻译手册”：

• 第一本手册：记录 s 里的字母 → 应该翻译成 t 里的哪个字母。
• 第二本手册：记录 t 里的字母 → 是从 s 里的哪个字母翻译来的。

为什么需要两本？因为规则是双向的：如果 s 里的 'e' 翻译成 'a'，那么反过来，'a' 只能由 'e' 翻译过来，不能由别的字母翻译过来。所以两本手册互相印证，确保没有冲突。

你从左到右，一个字母一个字母地看： 1. 先看 s 的当前字母，查第一本手册：如果手册里已经记过它，那它必须翻译成手册里记的那个字母，如果和 t 的当前字母不一样，就说明规则矛盾，直接失败。 2. 再看 t 的当前字母，查第二本手册：如果手册里已经记过它，那它必须是由手册里记的那个 s 字母翻译来的，如果和 s 的当前字母不一样，也说明矛盾，失败。 3. 如果两本手册都没记过这对字母，那就把这对关系记下来：第一本记 s→t，第二本记 t→s。

这个过程就像你一边走一边建立翻译规则，如果遇到冲突就说明不可能，如果顺利走完所有字母，就说明可以。

代码逐步拆解

我们来看参考代码，一行一行解释。

HashMap<Character, Character> dic1 = new HashMap<>();
HashMap<Character, Character> dic2 = new HashMap<>();

• 创建两个“字典”（HashMap），用来当翻译手册。
• dic1 存的是 s 里的字符 → t 里的字符。
• dic2 存的是 t 里的字符 → s 里的字符。

for (int i = 0; i < s.length(); i++) {
    char sChar = s.charAt(i);
    char tChar = t.charAt(i);

• 循环遍历每个位置 i，取出 s 和 t 在这一位置的字符，分别叫 sChar 和 tChar。

if (dic1.containsKey(sChar) && dic1.get(sChar) != tChar) {
    return false;
}

• 检查第一本手册：如果 sChar 已经记过了（dic1.containsKey(sChar)），那么它应该翻译成 dic1.get(sChar) 这个字符。如果这个字符不等于当前的 tChar，说明规则矛盾，返回 false。

if (dic2.containsKey(tChar) && dic2.get(tChar) != sChar) {
    return false;
}

• 检查第二本手册：如果 tChar 已经记过了（dic2.containsKey(tChar)），那么它应该是由 dic2.get(tChar) 这个字符翻译来的。如果这个字符不等于当前的 sChar，也说明矛盾，返回 false。

if (!dic1.containsKey(sChar)) {