题目描述

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

如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。

所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。

样例1

输入: s = "egg", t = "add"
输出: true

样例2

输入: s = "foo", t = "bar"
输出: false

样例3

输入: s = "paper", t = "title"
输出: true

说明

你可以假设 s 和 t 具有相同的长度。

算法

(哈希表) $O(n)$

本题与 LeetCode 290. Word Pattern 类似， 将题意抽象出来就是问我们两个长度为n的字符串s和t能否按顺序构成一个一一对应关系。一个一一对应关系即 相同的值对应相同的像，不同的值对应不同的像。其中不同的值对应不同的像等价于相同的像对应相同的值 (逆否命题)，即 $值 \leftrightarrow 像$。而哈希表可以以键值对的形式存储键key到值value的映射，即 $key \rightarrow value$，那么我们开两个哈希表分别保存值与像和像与值之间的关系就好了。

参考文献

wikipedia： 单射

C++ 代码

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        unordered_map<char, char> st, ts;
        for (int i = 0; i < s.size(); i ++ )
        {
            // 相同的值对应相同的像
            if (st.count(s[i]) && st[s[i]] != t[i]) return false;
            // 相同的像对应相同的值
            if (ts.count(t[i]) && ts[t[i]] != s[i]) return false;

            st[s[i]] = t[i];
            ts[t[i]] = s[i];
        }
        return true;
    }
};