Isomorphic Strings
題目描述:給定兩個字串 s 和 t,判斷它們是否同構(isomorphic)。同構表示 s 中的每個字元都能被一個唯一字元替換以得到 t,且這個映射必須是一對一的(bijective)——即 s 中不同字元不可映射到相同字元,且同一字元必須始終映射到同一字元。
解題思路:使用兩個雜湊表同時維護雙向映射關係:s2t 記錄 s 中字元到 t 中字元的映射,t2s 記錄 t 中字元到 s 中字元的反向映射。逐位掃描兩個字串,對每個位置 i:
- 若
s[i] 已有映射但映射目標不是 t[i],則矛盾,回傳 false。
- 若
t[i] 已有反向映射但反向映射來源不是 s[i],則代表 t[i] 被兩個不同的 s 字元共用,違反一對一,回傳 false。
- 否則建立(或確認)雙向映射,繼續下一個位置。
全部掃描完畢若無矛盾,則回傳
true。
時間複雜度:O(n) — 對兩個字串進行一次線性掃描,每次雜湊表的查詢與插入操作平均為 O(1),整體為 O(n),其中 n 為字串長度。
空間複雜度:O(1) — 兩個雜湊表的大小受字元集大小限制(最多 256 個 ASCII 字元),與字串長度無關,視為常數空間。
方法一:雙雜湊表雙向映射 O(n)(本題主要解法)
如上,同時維護 s→t 與 t→s 兩個映射,確保一對一關係。時間 O(n),空間 O(1)(字元集有限)。
方法二:記錄各字元最後出現索引 O(n)
對每個位置 i,同時查詢 s[i] 在 s 中最後一次出現的索引,以及 t[i] 在 t 中最後一次出現的索引,若兩者相同則代表映射一致;否則回傳 false。使用兩個長度 256 的陣列分別記錄各字元上次出現的位置(初始化為 -1),時間 O(n)、空間 O(1)。
方法三:正規化字串比較 O(n)
分別將 s 和 t 都轉換成「首次出現順序編碼」的正規化字串(例如 "egg" → "0 1 1"、"add" → "0 1 1"),若兩者正規化結果相同則同構。時間 O(n),空間 O(n)(需儲存正規化字串),直觀但空間較高。