題目出處

205. Isomorphic Strings

難度

easy

個人範例程式碼

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        if not s or not t:
            return False

        if len(s) != len(t):
            return False

        s_to_t = {}
        t_to_s = {}

        for i in range(len(s)):
            if s[i] in s_to_t and t[i] in t_to_s:
                if s_to_t[s[i]] == t[i] and t_to_s[t[i]] == s[i]:
                    continue
                else:
                    return False
            else:
                if s[i] in s_to_t: # one side alraedy exist
                    return False

                if t[i] in t_to_s:
                    return False

                s_to_t[s[i]] = t[i]
                t_to_s[t[i]] = s[i]

        return True

算法說明

注意：來回雙向都要配對

這題要注意的點就是「雙向配對」，因為如果只有單向配對時，有可能出現 “abcd” 也能 matching “ssss” 的情況。

(因為 hashmap 中存的東西，不論 a,b,c,d 都對應到 s)

input handling

處理 len(s) != len(t) 的情況，處理 s 或 t 不存在值的情況。

Boundary conditions

用 for 來控制範圍

Reference

• 字符同构 · Isomorphic Strings