title: 每日一练（43）：同构字符串
categories:[剑指offer]
tags:[每日一练]
date: 2022/04/15
每日一练（43）：同构字符串
给定两个字符串 s 和 t ，判断它们是否是同构的。
如果 s 中的字符能够按某种映射关系替换失去 t ，那么这两个字符串是同构的。
每个呈现的字符都该当映射到另一个字符，同时不扭转字符的程序。不同字符不能映射到同一个字符上，雷同字符只能映射到同一个字符上，字符能够映射到本人自身。
示例 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 字符组成
起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
办法一
思路剖析
t.length == s.length 所以无需思考长度
雷同的字符用find找到的index肯定是一样的
利用这点咱们能够利用find来验证是否pattern雷同
- 假如有foo和baa，当咱们到最初一个index时s里找'o'和t里找'a'肯定会返回
- 雷同的index，因为之前曾经呈现过了，这里s里的'o'跟t里的'a'都会返回index 1
- 再假如咱们有foo和bar，'fo'和'ba'是没有问题的，然而当咱们到最初一个index时
- s里的'o'会返回1，因为之前曾经呈现过，而t里的'r'会返回2，因为之前并没有
- 呈现过这个字母，这样就能够验证他们的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;}办法二
思路剖析
为具备对应关系的字符连边并赋予权值，初始值为 0 示意未有映射关系，同为 0 能力连边
因而如果是同构字符串，每对字符的值应该相等
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;}