华为 OD 训练营 · 题解精讲

LC205. 同构字符串

题目描述

给定两个字符串 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 的字符一一映射。由于映射是双向的（不同字符不能映射到同一字符），需要同时维护 s→t 和 t→s 两个方向的映射关系。

参考代码使用两个哈希表 dic1 和 dic2 分别存储 s→t 和 t→s 的映射。遍历字符串时，对于每一对字符 (s[i], t[i])，检查两个方向的映射是否一致：若某个方向已存在映射但值与当前字符不符，则返回 False；否则将新的映射关系存入两个哈希表。

关键步骤

1. 初始化两个空字典 dic1（s→t）和 dic2（t→s） 2. 遍历下标 i 从 0 到 len(s)-1：

若 s[i] 已在 dic1 中且 dic1[s[i]] != t[i]，返回 False
若 t[i] 已在 dic2 中且 dic2[t[i]] != s[i]，返回 False
若 s[i] 不在 dic1 中，添加映射 dic1[s[i]] = t[i]
若 t[i] 不在 dic2 中，添加映射 dic2[t[i]] = s[i]

3. 遍历结束返回 True

以 s="egg", t="add" 为例的映射过程：


i=0: s[0]='e' → t[0]='a'   dic1={'e':'a'}, dic2={'a':'e'}
i=1: s[1]='g' → t[1]='d'   dic1={'e':'a','g':'d'}, dic2={'a':'e','d':'g'}
i=2: s[2]='g' → t[2]='d'   dic1['g']='d' 与 t[2]='d' 一致，通过

复杂度分析

时间复杂度：O(n)，其中 n 为字符串长度。只需一次线性遍历，哈希表的查找和插入均为 O(1)。
空间复杂度：O(k)，k 为不同字符的数量，最坏情况下 k = n（所有字符不同），即 O(n)。

参考代码

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:

        # 设置一个哈希集合用来存储字符串 s 当中的元素
        dic1 = {}

        # 设置一个哈希集合用来存储字符串 t 当中的元素
        dic2 = {}

        # 由于 t.length == s.length
        # 按照顺序访问 s 和 t 中对应的元素
        for i in range(len(s)):

            # 1、访问的元素 s[i] 存在于 dic1 中
            # 并且发现它对应的元素值和当前 t 中元素 t[i] 不相同
            # 返回 False
            if s[i] in dic1 and dic1[s[i]] != t[i]:
                return False

            # 2、访问的元素 t[i] 存在于 dic2 中
            # 并且发现它对应的元素值和当前 s 中元素 s[i] 不相同
            # 返回 False
            if t[i] in dic2 and dic2[t[i]] != s[i]:
                return False

            # 3、访问的元素 s[i] 不存在于 dic1 中
            # 存放到哈希集合中
            if s[i] not in dic1:
                # dic1[s[i]] = t[i]
                dic1[s[i]] = t[i]

            # 3、访问的元素 t[i] 不存在于 dic2 中
            # 存放到哈希集合中
            if t[i] not in dic2:
                # dic2[t[i]] = s[i]
                dic2[t[i]] = s[i]
        # 返回 True
        return True

← 上一篇

LeetCode200、岛屿数量

LC207. 课程表