0205. Isomorphic Strings (Easy)
Question
Given two strings *s * and *t *, determine if they are isomorphic.
Two strings are isomorphic if the characters in *s * can be replaced to get *t *.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.
Example 1
| |
Example 2
| |
Example 3
| |
分析/解題
給定兩個字串s和t，試判斷它們是否同構(isomorphic)
若s和t同構，表示可以透過將s中的相同的字元轉換成另一個字元，
保有其順序，使得在轉換過後的s和t完全一樣。
兩個不同的字元不可映射到相同的字元 ，
但一個字元可以映射到原來的字元(也就是不變)。
這個題目簡而言之，就是在找尋用特定方式轉換對應字的方法，
比如範例中的paper -> title有以下的轉換對應：
p <-> t, a <-> i, e <-> l, r <-> e
由於同構並沒有限制轉換方向，所以既要轉得過去，也要轉得回來，
這代表了他們對應必須要1對1才行。
因此，我們可以想到以下的方式：
- 先檢查兩邊長度，不相等則直接回傳False (怎麼轉都沒用XD)
- 可以選擇建立一個HashMap/Dict 並額外處理雙向 的對應檢查，
或者選擇開出2個陣列/Dict(也可用串列，不過要自己轉換) 來做檢查。 - 每次從s, t中各取出一個字元 (假設現在在index i )：
3-1. 兩字元都未進入 陣列對應 -> 將s[i] 與t[i] 放入兩個陣列的對應
3-2. 兩字元都進入 陣列對應 -> 檢查s[i] 是否對到t[i] ，t[i] 是否對到s[i]
(只要其中一個對錯或沒對到，即可判定為False ) - 當所有字元均檢查完，表示順利全數對應到，回傳True 。
簡單吧！
在Java的部份，
我們可以直接利用char可以自動轉換成int當作陣列的index。
沒有對應則會拿到預設值(0)，依此寫成以下程式碼：
Java
Python的部份，方便起見我們使用了dict來紀錄，
預設值使用get放入0。
另外提供一個特別的用法，可以使用maketrans 及translate ，
來進行兩個表的轉換。但由於中間可能有重複，
所以要先經過set(刪去重複)和list, join 以後，
重新依照原先的字母排列排序(用key＝s.index) ，
最終看看s經過轉換以後是否和t相同。
Python
面試實際可能會遇到的問題
「時間/空間複雜度？」
(O(N)/O(N), 但空間複雜度最高取決於實際用到的字數，
亦可視為O(1)，因限縮在ASCII Code的話也才128種類)
相似及延伸
Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)
從LeetCode學演算法，我們下次見囉，掰~
感謝大家對這系列文章的支持！這邊跟大家自我工商一下：
筆者開設的系列同名線上課程：
「從Leetcode學演算法｜基礎篇」已經上線啦！ 在這堂課中，你將學會利用十種演算法/資料結構來優化解題過程，
並實際完整練習20題 精選考古題，
進而逐漸提升到不需提示也可以突破白板題，取得工作門票！
限額早鳥連結： https://hiskio.com/courses/319?promo_code=13L5QJE
問卷抽書＆取得上架通知： https://pse.is/MS2J2
如果你對線上課程不放心，
也可以先來12/17(二) 我在天瓏分享的講座看看！
講座連結： https://pse.is/JS3LJ