205. 同构字符串

🟢   🔖  哈希表 字符串  🔗 力扣 LeetCode

题目

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^4
• t.length == s.length
• s and t consist of any valid ascii character.

题目大意

给定两个字符串 s 和 t ，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

解题思路

1. 哈希表记录字符映射关系：使用两个哈希表 map1 和 map2 分别记录字符从字符串 s 映射到字符串 t 的关系，以及字符从字符串 t 映射到字符串 s 的关系。

2. 遍历字符串并检查映射关系：遍历字符串 s 和 t 的每个字符，分别检查当前字符在 map1 和 map2 中的映射关系。

3. 判断是否满足同构条件：如果当前字符在 map1 中的映射关系不为空，且映射关系不等于当前字符在 t 中的字符，或者当前字符在 map2 中的映射关系不为空，且映射关系不等于当前字符在 s 中的字符，则不满足同构条件，返回 false。

4. 返回结果：如果遍历完字符串没有发现不同构的情况，返回 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;
};

相关题目

题号	标题	题解	标签	难度
290	单词规律	[✓]	哈希表 字符串
890	查找和替换模式		数组 哈希表 字符串