关于leetcode:每日一练43同构字符串

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 雷同

1. 假如有 foo 和 baa，当咱们到最初一个 index 时 s 里找 ’o’ 和 t 里找 ’a’ 肯定会返回
2. 雷同的 index，因为之前曾经呈现过了，这里 s 里的 ’o’ 跟 t 里的 ’a’ 都会返回 index 1
3. 再假如咱们有 foo 和 bar，’fo’ 和 ’ba’ 是没有问题的，然而当咱们到最初一个 index 时
4. s 里的 ’o’ 会返回 1，因为之前曾经呈现过，而 t 里的 ’r’ 会返回 2，因为之前并没有
5. 呈现过这个字母，这样就能够验证他们的 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;
}