切換
舊版
前往
大廳
主題

LeetCode - 205. Isomorphic Strings 解題心得

Not In My Back Yard | 2020-09-10 00:09:48 | 巴幣 2 | 人氣 391

題目連結:


題目意譯:
給定兩字串 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] 這個字元設為「被」映射過了。然後繼續到下一個字元。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作