題目描述:給定兩個字串 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 字元),與字串長度無關,視為常數空間。
1. Initialize two hash maps: s2t (s char to t char) and t2s (t char to s char).
2. For each index i from 0 to len(s)-1:
a. Let sc = s[i], tc = t[i].
b. If sc is already in s2t:
- If s2t[sc] != tc: return false (s character maps to different t character).
c. Else: record s2t[sc] = tc.
d. If tc is already in t2s:
- If t2s[tc] != sc: return false (t character mapped from different s character).
e. Else: record t2s[tc] = sc.
3. Return true (all mappings are consistent and bijective).方法一:雙雜湊表雙向映射 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)(需儲存正規化字串),直觀但空間較高。