205. Isomorphic Strings

題目 / Problem

中文： 給定兩個字串 s 和 t，判斷它們是否「同構（isomorphic）」。

如果 s 中的字元可以「替換」後得到 t，這兩個字串就是同構的。規則是：

• 某個字元的所有出現位置，都必須換成同一個目標字元，並且保持順序不變。
• 兩個不同的字元不可以映射到同一個目標字元（映射必須是一對一的）。
• 一個字元可以映射到它自己。

English: Given two strings s and t, decide whether they are isomorphic.

They are isomorphic if the characters in s can be replaced to produce t, under these rules:

• Every occurrence of a character must be replaced by the same target character, preserving order.
• No two distinct characters may map to the same target character (the mapping is one-to-one).
• A character may map to itself.

Constraints / 約束： - 1 <= s.length <= 5 * 10^4 - t.length == s.length（兩字串等長 / same length） - s 和 t 可以是任意有效 ASCII 字元 / any valid ASCII characters.

Worked example / 範例： s = "egg", t = "add" → true。'e'→'a'，'g'→'d'（g 出現兩次都對應 d），所以同構。

名詞解釋 / Glossary

• 同構 / Isomorphic： 兩字串之間存在一個一對一且保持結構的字元對應關係。換句話說，把 s 的每個字元固定換成某個字元後能變成 t，且這個對應是雙向唯一的。
• 映射 / Mapping： 一條「某字元 → 某字元」的規則。本題需要兩個方向的映射：s→t 和 t→s，兩個都要一致才算同構。
• 雜湊表 / Hash map： 一種以「鍵 → 值」儲存資料的結構，查詢和插入平均都是 O(1)。我們用它記住「某個字元已經對應到哪個字元」。
• 陣列當查表 / Array as lookup table： 當鍵是 ASCII 字元（只有 256 種）時，可以直接用一個大小 256 的陣列代替雜湊表，用字元的數值當索引，速度更快、更簡單。
• 不變量 / Invariant： 演算法執行過程中始終保持為真的性質。本題的不變量是：「目前為止建立的所有映射都互相一致、且一對一」。

思路

中文：最直接的暴力想法是，對每一對字元 (s[i], t[i])，去檢查前面是否出現過矛盾。但若每次都往回掃描整個字串，時間會變成 O(n²)，在長度達 5×10⁴ 時太慢。關鍵觀察是：同構的本質是「字元之間的對應關係」，我們其實不需要回頭掃描，只要記住每個字元第一次出現時被對應到什麼，之後再遇到時直接比對是否一致即可。所以我們用兩張查表：mapST 記錄 s 的字元應該對應到 t 的哪個字元，mapTS 記錄反方向。為什麼需要兩個方向？因為題目有兩條規則：同一個 s 字元不能對應到不同的 t 字元（這是 mapST 管的），而且不同的 s 字元不能對應到同一個 t 字元（這是 mapTS 管的，也就是一對一）。逐字掃描時，對每一對 (a, b)：若 mapST[a] 已有值但不等於 b，矛盾，回傳 false；若 mapTS[b] 已有值但不等於 a，矛盾，回傳 false；否則建立或確認這兩條映射。整個字串掃完都沒矛盾就是同構。由於每個字元只看一次、查表是 O(1)，總時間是 O(n)。

English: The naive idea is, for each pair (s[i], t[i]), to scan backwards checking for a conflict — but that is O(n²) and too slow at length 5×10⁴. The key insight is that isomorphism is purely about a consistent character correspondence, so we don't need to look back: we just remember what each character was first mapped to, and verify consistency on later occurrences. We keep two lookup tables: mapST (what each s character must become in t) and mapTS (the reverse). Why two directions? Because there are two rules: one s character can't map to two different t characters (guarded by mapST), and two different s characters can't map to the same t character (guarded by mapTS, i.e. the mapping must be one-to-one). Walking through the strings once, for each pair (a, b): if mapST[a] already exists but differs from b, conflict → false; if mapTS[b] already exists but differs from a, conflict → false; otherwise record/confirm both directions. If we finish with no conflict, the strings are isomorphic. Each character is visited once with O(1) lookups, so the total time is O(n).

逐步走查 / Walkthrough

以 s = "egg", t = "add" 為例 / Using s = "egg", t = "add".

我們用 0 代表「尚未建立映射」（因為合法字元值都 > 0，可用 0 當空白標記）。 We use 0 to mean "no mapping yet" (valid chars are > 0, so 0 is a safe sentinel).

掃描結束，無矛盾 → 回傳 true。 Loop finished with no conflict → return true.

（對照失敗例 s="ab", t="aa"：i=1 時 mapTS['a'] 已是 'a'，但現在的 s 字元是 'b'≠'a'，違反一對一 → false。） (Contrast: s="ab", t="aa": at i=1, mapTS['a'] is already 'a' but the current s char is 'b' → not one-to-one → false.)

Solution — C

// 演算法 / Algorithm:
// 用兩張大小 256 的查表記錄 s→t 與 t→s 的字元映射，掃描一次；
// 每對字元都要與已存在的映射一致，且映射是一對一的，否則不同構。
// Two 256-sized lookup tables record s→t and t→s mappings; single pass.
// Each pair must agree with existing mappings and stay one-to-one, else not isomorphic.

#include <stdbool.h>   // 提供 bool / true / false / gives us the bool type
#include <string.h>    // 提供 strlen / gives us strlen

bool isIsomorphic(char* s, char* t) {
    // 兩張查表，索引是字元的 ASCII 值（0~255）/ two tables indexed by ASCII value (0..255)
    // 初始化全為 0，代表「尚未建立映射」/ initialized to 0, meaning "no mapping yet"
    // unsigned char 範圍 0~255，剛好涵蓋所有 ASCII / unsigned char 0..255 covers all ASCII
    unsigned char mapST[256] = {0};   // s 的字元 -> 應對應到的 t 字元 / s-char -> required t-char
    unsigned char mapTS[256] = {0};   // t 的字元 -> 應對應到的 s 字元 / t-char -> required s-char

    // 逐字掃描；t 與 s 等長，所以用同一個索引 i / scan char by char; equal length, share index i
    for (int i = 0; s[i] != ''; i++) {
        // 取出這一對字元，轉成 unsigned 避免負數索引 / read the pair as unsigned to avoid negative index
        unsigned char a = (unsigned char)s[i];   // s 端的字元 / character from s
        unsigned char b = (unsigned char)t[i];   // t 端的字元 / character from t

        if (mapST[a] == 0 && mapTS[b] == 0) {
            // 兩個方向都還沒映射 -> 第一次見到，建立雙向映射 / both unseen -> create both directions
            mapST[a] = b;   // 記住 a 以後必須變成 b / a must always become b
            mapTS[b] = a;   // 記住 b 以後必須來自 a / b must always come from a
        } else if (mapST[a] != b || mapTS[b] != a) {
            // 任一方向與既有映射不符 -> 矛盾 -> 不同構 / either direction disagrees -> conflict -> not isomorphic
            // mapST[a]!=b：a 之前對應到別的字元 / a was mapped to a different char before
            // mapTS[b]!=a：b 之前來自別的字元（破壞一對一）/ b came from a different char (breaks one-to-one)
            return false;
        }
        // 否則兩個方向都已存在且一致，什麼都不用做 / otherwise both exist and agree, nothing to do
    }

    // 全部掃完都沒矛盾 -> 同構 / no conflict over the whole string -> isomorphic
    return true;
}

Solution — C++

// 演算法 / Algorithm:
// 與 C 版相同：兩張查表記錄 s→t 與 t→s 的映射，單次掃描。
// 用陣列當查表（字元只有 256 種），比 unordered_map 更快更簡單。
// Same as C: two lookup tables for s→t and t→s, single pass.
// Arrays used as tables (only 256 possible chars) — faster/simpler than unordered_map.

#include <string>
#include <array>     // 提供固定大小陣列 std::array / fixed-size array container

class Solution {
public:
    bool isIsomorphic(std::string s, std::string t) {
        // std::array<int,256> 是固定大小陣列；{} 把每格初始化為 0
        // std::array<int,256> is a fixed-size array; {} zero-initializes every slot
        // 0 代表「尚未建立映射」(合法字元值 > 0) / 0 means "no mapping yet" (valid chars are > 0)
        std::array<int, 256> mapST{};   // s 字元 -> t 字元 / s-char -> t-char
        std::array<int, 256> mapTS{};   // t 字元 -> s 字元 / t-char -> s-char

        // range-for 取不到索引，這裡需要 i 同時索引 s 和 t，所以用傳統 for
        // a plain for loop because we need index i into both s and t at once
        for (std::size_t i = 0; i < s.size(); ++i) {
            // 轉成 unsigned char 再當索引，避免負值字元造成越界
            // cast to unsigned char before indexing, so high-bit chars don't go negative
            unsigned char a = static_cast<unsigned char>(s[i]);   // s 端字元 / char from s
            unsigned char b = static_cast<unsigned char>(t[i]);   // t 端字元 / char from t

            if (mapST[a] == 0 && mapTS[b] == 0) {
                // 第一次見到 -> 建立雙向映射 / first time seen -> set both directions
                mapST[a] = b;
                mapTS[b] = a;
            } else if (mapST[a] != b || mapTS[b] != a) {
                // 與既有映射矛盾 -> 不同構 / disagrees with existing mapping -> not isomorphic
                return false;
            }
            // 兩方向皆已存在且一致 -> 略過 / both exist and agree -> skip
        }

        // 全程無矛盾 -> 同構 / no conflict -> isomorphic
        return true;
    }
};

複雜度 / Complexity

• Time: O(n) — n 是字串長度。我們只掃描一次，每對字元做的都是常數時間的陣列查表與比較，沒有任何回頭掃描或巢狀迴圈，所以時間與長度成正比。 / We make a single pass; each pair costs constant-time array lookups and comparisons, no nested loops, so time is linear in the string length.
• Space: O(1) — 兩張查表大小固定為 256（與輸入長度無關），不論字串多長都只用這麼多額外空間，因此是常數空間。 / Two tables of fixed size 256, independent of input length, so extra space is constant.

Pitfalls & Edge Cases

• 只檢查一個方向 / Checking only one direction： 只用 mapST 會漏掉「兩個不同字元映射到同一字元」的情況（如 "ab"→"aa" 會被誤判為 true）。必須同時維護 mapTS 確保一對一。 / Using only mapST misses the "two chars map to the same target" case; you need mapTS for one-to-one.
• 負數索引 / Negative array index： char 在許多平台上有號，值 > 127 的 ASCII 字元當索引會變成負數而越界。先轉成 unsigned char 即可避免。 / char may be signed; cast to unsigned char before indexing to avoid negative indices.
• 空白標記與真實值衝突 / Sentinel collides with real value： 我們用 0 表示「未映射」。這是安全的，因為合法輸入字元（ASCII）值都不是用作真實映射目標的 0（'\0' 是字串結束符，不會出現在內容中）。 / 0 is the "unmapped" sentinel, safe because the null char '\0' never appears inside the content.
• 長度假設 / Length assumption： 題目保證 s 與 t 等長，所以可共用一個索引；若不保證，需先比長度。 / The problem guarantees equal length, so one index is fine; otherwise compare lengths first.
• 最短輸入 / Minimum input： 長度為 1（如 "a","a"）時迴圈跑一次建立映射後回傳 true，邊界正常。 / Length-1 inputs work: one iteration sets the mapping and returns true.