題目描述:
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
andt
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;
}
}