同构字符串

Q

给定两个字符串 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 * 104
• t.length == s.length
• s 和 t 由任意有效的 ASCII 字符组成

A

• 一一映射，从s到t，从t到s，只一边满射不可以
• 字符到字符的映射 -> 两边字符到位置的映射
• 不用哈希表，因为可能的键的范围是非负char

bool isIsomorphic(string s, string t)
{
    if (s.size() != t.size())
        return false;
    // char to pos
    // char only contain 128 nonnegative values (which represents all ASCII char)
    size_t smap[128] = {0};
    size_t tmap[128] = {0};
    char sc, tc;
    for (size_t i = 0, sz = s.size(); i < sz; ++i)
    {
        sc = s[i];
        tc = t[i];
        if (smap[sc] != tmap[tc])
            return false;
        // smap[sc] == tmap[tc]:
        // 1. both 0: sc and tc haven't been mapped to any pos
        // 2. both non zero: sc and tc have been mapped to the same pos
        smap[sc] = i + 1; // pos: i+1 for 0 represents haven't been mapped to any pos
        tmap[tc] = i + 1;
    }
    return true;
}