題目連結:
題目意譯:
給定兩字串 s 、 t ,判斷他們是否同構(Isomorphic)
如果字串 s 裡的字元可以被替換成別的字元而得到字串 t,則兩字串為同構。
所有同樣的字元必須替換成同一個字元,並且保持字元之間的相對位置。沒有兩個字元可以映射到同一個字元,但是一個字元可以映射到自己(也就是維持不變)。
注:
你可以假設 s 與 t 長度相同。
範例測資:
範例 1:
輸入: s = "egg",t = "add"
輸出: true
範例 2:
輸入: s = "foo",t = "bar"
輸出: false
範例 3:
輸入: s = "paper",t = "title"
輸出: true
解題思維:
s 要跟 t 是同構的,也就表示 s 的每個字元可以對應到 t 的每個字元,而同一種字元要映射到一樣的字元。
掃過字串 s 。假設現在是第 i 個字元,判斷 s[i] 是否已經在先前有過映射。如果沒有,判斷 t[i] 是否有「被」映射過,如果有就表示無法一一對應,則回傳假(False);而如果 s[i] 有映射,但是其映射的字元卻不等於 t[i] ,這樣的情況也代表不能一一對應,也是回傳假。
如果上述的判斷都過了,則將 s[i] 的映射設為 t[i] ,且將 t[i] 這個字元設為「被」映射過了。然後繼續到下一個字元。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。