Description
給定兩個字串
s和t，判斷它們是否同構。兩個字串同構意味著s中的字元可以被替換成t中對應的字元，且映射必須是一對一的（不同字元不能映射到同一個字元）。
Example:
Input: s = “egg”, t = “add” Output: true
Intuition#
核心思路：建立雙向映射，確保
s → t和t → s的映射都是一對一的。
- 光有
s → t的映射不夠，例如s = "badc",t = "baba"中d → b和b → b會衝突 - 需要雙向檢查：每個
s的字元只能映射到一個t的字元，反之亦然
Approaches#
1: 雙 HashMap#
- 概念: 用兩個 HashMap 分別記錄
s → t和t → s的映射 - 時間複雜度:
O(n)- 遍歷一次字串 - 空間複雜度:
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: 首次出現位置比較#
- 概念: 對每個位置
i，比較s[i]在s中首次出現的位置和t[i]在t中首次出現的位置，若不同則不同構 - 時間複雜度:
O(n^2)-indexOf每次 O(n)；但概念簡潔 - 空間複雜度:
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
}
}雖然首次出現位置法概念簡潔，但因
indexOf是 O(n) 操作，整體時間複雜度為 O(n^2)。面試中推薦使用雙 HashMap 的 O(n) 解法。
補充：使用陣列代替 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: 雙向映射驗證是同構/模式匹配問題的標準做法
- 關鍵技巧: 只有單向映射會遺漏「多對一」的情況；用陣列紀錄「上次出現位置」是一個優雅的替代方案