刷题日记-205. 同构字符串-一一网

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

一、题目描述

205. 同构字符串 – 力扣（LeetCode） (leetcode-cn.com)

给定两个字符串 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 字符组成

二、思路分析

整体思想：使用哈希表用于记录s和t的一一对应关系，当出现不满足的情况，就返回False；遍历结束后，就返回True

构建一个字典，用于存放映射关系
遍历字符串s，对于每一个s[i]，如果已经存在于字符串中，则核对该s[i]的值与t[i]是否相匹配，如果不匹配，则返回False；如果未存在于字符串中，则核对t[i]的值是否已经存在于值列表中，如果已经存在，则返回False，否则，将该s[i]-t[i]映射保存在字典中。
遍历结束后，返回True

三、AC 代码

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        res_dict = {}
        n = len(s)
        for i in range(n):
            if s[i] in res_dict:
                if res_dict[s[i]] != t[i]:
                    return False
            else:
                if t[i] in res_dict.values():
                    return False
                res_dict[s[i]] = t[i]
        return True
复制代码