[LeetCode刷題筆記] 205 – Isomorphic Strings

題目描述:

Given two strings s and t, determine if they are isomorphic.

Two strings s and t 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:

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

Example 2:

Input: s = "foo", t = "bar"
Output: false

Example 3:

Input: s = "paper", t = "title"
Output: true

 

Constraints:

  • 1 <= s.length <= 5 * 104

  • t.length == s.length

  • s and t consist of any valid ascii character.

一刷題解(Dictionary):

        這道題需要我們驗證兩個字符串是否「同構」的。「同構」就是指一個字符串中的字符與另一個字符串裡的字符是完全1對1的,比如這裡有一對「同構」的字符串,字符串A為”egg”,字符串B為”add”。字符串A的’e’對應字符串B的’a’;字符串A的’g’對應字符串B的’d’。基於這個「1對1」的特性,我們可以構造一個字典存儲兩個字符串中的字符的對照關係。

        我們遍歷其中一個字符串(比如arrA),對每個字符進行檢查。第一個檢查是「字典裡面是否有以這個字符為鍵的條目」,有的話就代表我們已經建立了這個字符的對應關係,然後檢查另一個字符串(arrB)中的當前字符是否與字典中的對應值一致,如果不是,就代表這兩個字符串不是同構的。

        第二個檢查是,當字典裡面沒有以當前字符為鍵的條目時,基於字符串之間的字符是1對1的關係這一點,如果A字符串中下標為2的字符不存在於字典裡,同樣地,B字符串中下標為2的字符也不應該存在於字典中。如果A的字符不存在而B的字符存在字典裡,那A和B也不是「同構」的。

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++)
        {
//檢查字典裡是否有以A字符串中的字符為鍵的條目            if(charDict.ContainsKey(s[i]))           {               if(charDict[s[i]] != t[i]){ return false; }           }            else           {
//如果在當前下標中,字典裡沒有以A字符串中的字符為鍵的條目,那B字符串當前下標的字符也不應該存在於字典裡                if(charDict.ContainsValue(t[i])){ return false; }

//建立對應關係(Key:A字符串的字符;Value:B字符串的字符)                charDict.Add(s[i], t[i]);           }       }                return true;   } }