LeetCode 205. 同構字符串：雙哈希表解法詳解

題目描述

給定兩個字符串 s 和 t，判斷它們是否同構。同構定義為：s 中的字符可以被替換得到 t，所有相同字符必須映射到同一字符，且不同字符不能映射到同一字符（但字符可映射到自身）。假設兩字符串長度相等。

示例：

• s = "egg", t = "add" → true
• s = "foo", t = "bar" → false
• s = "paper", t = "title" → true

解題思路：雙向映射檢查

為確保一對一映射關係，需同時維護兩個映射表：

1. s → t 映射：記錄 s 中每字符對應的 t 字符。
2. t → s 映射：記錄 t 中每字符對應的 s 字符，防止兩個不同字符映射到同一字符。

遍歷字符串，若發現映射衝突則返回 false；遍歷結束無衝突則返回 true。

C++ 代碼實現

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        int map_s[256] = {0}; // s -> t 映射，0 表示未映射
        int map_t[256] = {0}; // t -> s 映射
        string transformed = "";

        for (int i = 0; i < s.size(); ++i) {
            char cs = s[i], ct = t[i];

            // 建立 s -> t 映射
            if (map_s[cs] == 0) map_s[cs] = ct;
            // 建立 t -> s 映射
            if (map_t[ct] == 0) map_t[ct] = cs;
            else if (map_t[ct] != cs) return false; // 衝突：t 中字符已映射到不同的 s 字符

            transformed.push_back(map_s[cs]);
        }
        return transformed == t;
    }
};

關鍵點解析

• 使用大小為 256 的整型數組模擬哈希表，下標為字符 ASCII 碼，值為映射目標字符（0 表示未映射）。
• 雙向檢查確保雙射關係：map_t[ct] != cs 捕獲「一對多」情況。
• 構建 transformed 字符串驗證最終映射結果是否等於 t，邏輯清晰直觀。

複雜度

• 時間：O(n)，單次遍歷。
• 空間：O(1)，固定大小數組（256×2）。