給定兩個字串
s和t，判斷它們是否同構。兩個字串同構意味著s中的字元可以被替換成t中對應的字元，且映射必須是一對一的（不同字元不能映射到同一個字元）。
Example:
Input: s = “egg”, t = “add” Output: true
Intuition
TIP
核心思路：建立雙向映射，確保 s → t 和 t → s 的映射都是一對一的。
- 光有
s → t的映射不夠，例如s = "badc",t = "baba"中d → b和b → b會衝突 - 需要雙向檢查：每個
s的字元只能映射到一個t的字元，反之亦然
Approaches
1. Two HashMaps — O(n) / O(n)
- Idea: 用兩個 HashMap 分別記錄
s → t和t → s的映射 - Time:
O(n)- 遍歷一次字串 - Space:
O(n)- 兩個 Map
class Solution {
fun isIsomorphic(s: String, t: String): Boolean {
val mapST = HashMap<Char, Char>()
val mapTS = HashMap<Char, Char>()
for (i in s.indices) {
val cs = s[i]
val ct = t[i]
if (mapST.containsKey(cs) && mapST[cs] != ct) return false
if (mapTS.containsKey(ct) && mapTS[ct] != cs) return false
mapST[cs] = ct
mapTS[ct] = cs
}
return true
}
}⭐ 2. Compare First-Occurrence Index — O(n^2) / O(1)
- Idea: 對每個位置
i，比較s[i]在s中首次出現的位置和t[i]在t中首次出現的位置，若不同則不同構 - Time:
O(n^2)-indexOf每次 O(n)；但概念簡潔 - Space:
O(1)- 不需要額外空間
class Solution {
fun isIsomorphic(s: String, t: String): Boolean {
for (i in s.indices) {
if (s.indexOf(s[i]) != t.indexOf(t[i])) return false
}
return true
}
}WARNING
雖然首次出現位置法概念簡潔，但因 indexOf 是 O(n) 操作，整體時間複雜度為 O(n^2)。面試中推薦使用雙 HashMap 的 O(n) 解法。
Note: Array instead of HashMap
因為字元集有限（ASCII 128），可以用陣列代替 HashMap 來加速。
class Solution {
fun isIsomorphic(s: String, t: String): Boolean {
val mapS = IntArray(128)
val mapT = IntArray(128)
for (i in s.indices) {
if (mapS[s[i].code] != mapT[t[i].code]) return false
mapS[s[i].code] = i + 1
mapT[t[i].code] = i + 1
}
return true
}
}🔑 Takeaways
- Pattern: 雙向映射驗證是同構/模式匹配問題的標準做法
- Key trick: 只有單向映射會遺漏「多對一」的情況；用陣列紀錄「上次出現位置」是一個優雅的替代方案