205.同构字符串

题目:205.同构字符串

给定两个字符串 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 字符组成

思路

可以通过使用两个哈希表来实现判断两个字符串是否同构。具体思路如下：

1. 初始化哈希表：分别用 mapS2T 和 mapT2S 记录字符串 s 和 t 中字符的映射关系。
2. 遍历字符串：通过遍历字符串 s 和 t，检查并更新映射关系。
3. 检查映射关系：在遍历过程中，先检查当前字符是否已有映射关系，如果有则检查映射关系是否匹配，如果没有则更新映射关系。
4. 返回结果：如果所有字符的映射关系都匹配，则返回 true，否则返回 false。

• 时间复杂度:O(n)
• 空间复杂度:O(1)

代码

public boolean isIsomorphic(String s, String t) {
    // 哈希表记录 s -> t 的映射关系
    HashMap<Character, Character> mapS2T = new HashMap<>();
    // 哈希表记录 t -> s 的映射关系
    HashMap<Character, Character> mapT2S = new HashMap<>();
    // 检查 s -> t 的映射关系
    for (int i = 0; i < s.length(); i++) {
        char charS = s.charAt(i);
        char charT = t.charAt(i);
        if (mapS2T.containsKey(charS)) {
            if (mapS2T.get(charS) != charT) {
                // 映射关系不匹配
                return false;
            }
        } else {
            mapS2T.put(charS, charT);
        }
    }
    // 检查 t -> s 的映射关系
    for (int i = 0; i < s.length(); i++) {
        char charS = s.charAt(i);
        char charT = t.charAt(i);
        if (mapT2S.containsKey(charT)) {
            if (mapT2S.get(charT) != charS) {
                // 映射关系不匹配
                return false;
            }
        } else {
            mapT2S.put(charT, charS);
        }
    }
    return true;
}