题目描述

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

如果存在一个字符到字符的双射，使得将 $s$ 中的字符映射后可以得到 $t$，我们就说 $s$ 和 $t$ 是同构的。

双射是指既是单射，又是满射。即字母要一一对应，相同字母映射到同一字母，不同字母映射到不同字母。

样例1

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

样例2

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

样例3

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

算法

(哈希表，映射) $O(n)$

我们要判断字母之间是否一一对应，即判断 $s$ 中的相同字母是否对应到 $t$ 中的相同字母，且 $t$ 中的相同字母是否对应到 $s$ 中的相同字母。

我们用两个哈希表分别存储 $s$ 到 $t$ 和 $t$ 到 $s$ 的映射关系。
然后从前往后扫描字符串，判断相同字符是否都映射到相同字符。

时间复杂度分析：哈希表的插入、查找操作的时间复杂度是 $O(1)$，两个字符串均只扫描一遍，所以总时间复杂度是 $O(n)$。

C++ 代码

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        unordered_map<char, char> st, ts;
        if (s.size() != t.size()) return false;
        for (int i = 0; i < s.size(); i ++ )
        {
            if (st.count(s[i]))
            {
                if (st[s[i]] != t[i]) return false;
            }
            else st[s[i]] = t[i];

            if (ts.count(t[i]))
            {
                if (ts[t[i]] != s[i]) return false;
            }
            else ts[t[i]] = s[i];
        }
        return true;
    }
};