title: 每日一練（43）：同構(gòu)字符串
categories:[劍指offer]
tags:[每日一練]
date: 2022/04/15
每日一練（43）：同構(gòu)字符串
給定兩個(gè)字符串 s 和 t ，判斷它們是否是同構(gòu)的。
如果 s 中的字符可以按某種映射關(guān)系替換得到 t ，那么這兩個(gè)字符串是同構(gòu)的。
每個(gè)出現(xiàn)的字符都應(yīng)當(dāng)映射到另一個(gè)字符般婆，同時(shí)不改變字符的順序。不同字符不能映射到同一個(gè)字符上，相同字符只能映射到同一個(gè)字符上哪轿，字符可以映射到自己本身。
示例 1:
輸入：s = "egg", t = "add"
輸出：true
示例 2：
輸入：s = "foo", t = "bar"
輸出：false
示例 3：
輸入：s = "paper", t = "title"
輸出：true
提示：
1 <= s.length <= 5 * 104
t.length == s.length
s 和 t 由任意有效的 ASCII 字符組成
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/isomorphic-strings
方法一
思路分析
t.length == s.length 所以無(wú)需考慮長(zhǎng)度
相同的字符用find找到的index一定是一樣的
利用這點(diǎn)我們可以利用find來(lái)驗(yàn)證是否pattern相同
假設(shè)有foo和baa翔怎，當(dāng)我們到最后一個(gè)index時(shí)s里找'o'和t里找'a'一定會(huì)返回
相同的index窃诉，因?yàn)橹耙呀?jīng)出現(xiàn)過(guò)了，這里s里的'o'跟t里的'a'都會(huì)返回index 1
再假設(shè)我們有foo和bar赤套，'fo'和'ba'是沒(méi)有問(wèn)題的飘痛，但是當(dāng)我們到最后一個(gè)index時(shí)
s里的'o'會(huì)返回1，因?yàn)橹耙呀?jīng)出現(xiàn)過(guò)容握，而t里的'r'會(huì)返回2宣脉，因?yàn)橹安](méi)有
出現(xiàn)過(guò)這個(gè)字母，這樣就可以驗(yàn)證他們的pattern是否相同
bool isIsomorphic(string s, string t) {
for (int i = 0; i < s.size(); ++i) {
if (s.find(s[i]) != t.find(t[i])) {
return false
}
}
return true;
}
方法二
思路分析
為具有對(duì)應(yīng)關(guān)系的字符連邊并賦予權(quán)值唯沮，初始值為 0 表示未有映射關(guān)系脖旱，同為 0 才能連邊
因此如果是同構(gòu)字符串，每對(duì)字符的值應(yīng)該相等
bool isIsomorphic(string s, string t) {
int sm[128] = {0};
int tm[128] = {0};
for (int i = 0; i < s.size(); i++) {
if (sm[s[i]] != tm[t[i]]) {
return false;
}
sm[s[i]] = tm[t[i]] = i + 1;
}
return true;
}
