題目在問什麼

給兩個字串 s 和 t，判斷它們是否 isomorphic。

意思是說，s 裡的每個字元都可以穩定地映射到 t 裡某個字元，而且：

  • 同一個字元不能前後映射成不同字元
  • 不同字元也不能映射到同一個目標字元

例子

Input: s = "egg", t = "add"
Output: true

解題思路

這題其實就是在檢查一對一映射是否成立。

最簡單的做法是用一個 Dictionary<char, char> 來記錄：

  • s[i] 之前是否已經對應到某個字元
  • 如果對應過，這次是不是還是同一個 t[i]
  • 如果沒對應過，則要確認 t[i] 目前沒有被別的字元佔用

為什麼要檢查雙向唯一性

只檢查 s -> t 還不夠。

例如：

  • ab
  • cc

如果只看單向映射，可能會覺得 a -> c、b -> c 都沒問題；但題目要求不同字元不能映射到同一個字元，所以這種情況必須回傳 false。

代碼

public class Solution
{
    public bool IsIsomorphic(string s, string t)
    {
        if (s == null && t == null) { return true; }
        if (s.Length != t.Length) { return false; }

        Dictionary<char, char> charDict = new Dictionary<char, char>();

        for (int i = 0; i < s.Length; i++)
        {
            if (charDict.ContainsKey(s[i]))
            {
                if (charDict[s[i]] != t[i]) { return false; }
            }
            else
            {
                if (charDict.ContainsValue(t[i])) { return false; }
                charDict.Add(s[i], t[i]);
            }
        }

        return true;
    }
}

複雜度

以上這份寫法因為用了 ContainsValue，所以最壞情況下：

  • 時間複雜度：O(n^2)
  • 空間複雜度：O(n)

如果要再優化，可以改成雙字典或兩個陣列，把時間壓到 O(n)。

這題先記住的重點

  • 這題本質是在驗證字元之間是否存在一對一映射
  • 只檢查單向對應不夠，還要防止不同字元撞到同一個目標
  • 題目不難，重點是把規則想完整