Leetcode 205. 同构字符串

205. 同构字符串

一、题目描述

给定两个字符串 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 * 10^4
• t.length == s.length
• s 和 t 由任意有效的 ASCII 字符组成

二、我的想法

1.最开始想的是将每个字符的出现次数都放在 defaultdict 中，如果这两个字符串所得的次数列表相等，那就说明这俩可以转换。但是没过去，37 / 46 个通过的测试用例。没过的那个测试用例为：s = “bbbaaaba”, t = “aaabbbba”。

class Solution:def isIsomorphic(self, s: str, t: str) -> bool:sdict = defaultdict(int)tdict = defaultdict(int)strLen = len(s)for i in range(strLen):sdict[s[i]] += 1tdict[t[i]] += 1slist = list(sdict.values())tlist = list(tdict.values())slist.sort()tlist.sort()return slist==tlist

2.又想了想，应该是字符与字符之间是对应关系。设置一个 dict ，遍历字符串，如果 s 对应的字符在 dict 中，判断对应的 t 的值是否与 dict 中的 value 值相等，如果不相等的话直接就返回 False 。如果直到遍历完字符串还没返回的话，就返回 True。

class Solution:def isIsomorphic(self, s: str, t: str) -> bool:compareDict = dict()sLen = len(s)for i in range(sLen):if s[i] not in compareDict:compareDict[s[i]] = t[i]else:if compareDict[s[i]] != t[i]:return Falsereturn True

3.结果又没过，38 / 46 个通过的测试用例，整半天就多通过了一个测试用例。想了想又加个判断条件：如果 s 对应的字符没在 dict 中，但是 t 对应的字符在 dict 中，返回 False。于是测试通过。

class Solution:def isIsomorphic(self, s: str, t: str) -> bool:compareDict = dict()sLen = len(s)for i in range(sLen):if s[i] not in compareDict :if t[i]  in compareDict.values():return FalsecompareDict[s[i]] = t[i]else:if compareDict[s[i]] != t[i]:return Falsereturn True

三、其他人的题解

看了一下大家的做法大概都是双向哈希表。

class Solution:def isIsomorphic(self, s: str, t: str) -> bool:mp1, mp2 = {}, {}for a, b in zip(s, t):if a in mp1 and mp1[a] != b:return Falseif b in mp2 and mp2[b] != a:return Falsemp1[a] = bmp2[b] = areturn True作者：Benhao
链接：https://leetcode.cn/problems/isomorphic-strings/solutions/1/python-zheng-fan-ha-xi-biao-ying-she-by-0si7q/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

其中 zip 函数的用法：
源码：zip([iterable, …])，iterable为迭代器，可以用列表、元组、字典、集合等。
主要功能：将其迭代器中的多个序列压缩成zip对象或者列表（版本不一样返回元素不一样），但其构成元素都是元组

来自于 码农研究僧的 Python zip函数 详解（全）