205. Isomorphic Strings
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 * 10^4t.length == s.lengthsandtconsist of any valid ascii character.
题目大意
给定两个字符串 s 和 t ，判断它们是否是同构的。
如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。
解题思路
哈希表记录字符映射关系：使用两个哈希表
map1和map2分别记录字符从字符串s映射到字符串t的关系，以及字符从字符串t映射到字符串s的关系。遍历字符串并检查映射关系：遍历字符串
s和t的每个字符，分别检查当前字符在map1和map2中的映射关系。判断是否满足同构条件：如果当前字符在
map1中的映射关系不为空，且映射关系不等于当前字符在t中的字符，或者当前字符在map2中的映射关系不为空，且映射关系不等于当前字符在s中的字符，则不满足同构条件，返回false。返回结果：如果遍历完字符串没有发现不同构的情况，返回
true。
- 时间复杂度：
O(n)，其中n是字符串的长度。 - 空间复杂度：
O(k)，其中k是字符集的大小。在本题中，由于字符集通常是有限的，所以空间复杂度是常数大小。
代码
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
var isIsomorphic = function (s, t) {
let map1 = new Map();
let map2 = new Map();
for (let i in s) {
// 检查 s 到 t 的映射关系
if (!map1.has(s[i])) {
map1.set(s[i], t[i]);
} else if (map1.get(s[i]) !== t[i]) {
return false;
}
// 检查 t 到 s 的映射关系
if (!map2.has(t[i])) {
map2.set(t[i], s[i]);
} else if (map2.get(t[i]) !== s[i]) {
return false;
}
}
return true;
};