LeetCode Isomorphic Strings：同構字串判斷

題目描述

給定字串 s, t，判斷是否同構：s 中字符可替換得到 t。所有相同字符必映射到同一字符，順序不變，雙向單射（可映射到自己）。

例："egg","add" → true；"foo","bar" → false；"paper","title" → true。

解法：雙向映射陣列

ASCII 256 字符，用兩個 unsigned char[256] 記錄雙向映射（0 表示未建立）。遍歷字串：

• 若雙向映射皆已建立，檢查一致性。
• 若皆未建立，建立映射。
• 否則（單向建立）返回 false。

比 Map/Hash 更快，O(1) 存取，無哈希開銷。

C++ 實現

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        vector<unsigned char> map1(256, 0), map2(256, 0);
        for (int i = 0; i < s.size(); ++i) {
            unsigned char c1 = s[i], c2 = t[i];
            unsigned char &m12 = map1[c2], &m21 = map2[c1];
            if (m12 && m21) {
                if (m12 != c1 || m21 != c2) return false;
            } else if (!m12 && !m21) {
                m12 = c1; m21 = c2;
            } else return false;
        }
        return true;
    }
};

複雜度

• 時間：O(N)。
• 空間：O(1)（固定 512 字節）。