Isomorphic Strings
如果可以通过重命名第一个字符串中的字符得到第二个字符串，那么这两个字符串就是同构的。同一个字符的每次出现都要使用相同的新名称，不同的字符不能使用相同的名称，字符也可以保留原来的名称。对于长度相同的两个字符串 s 和 t，如果它们同构，则返回 true；否则返回 false。
函数
- sstring
- 要重命名的字符串，字母和数字
- tstring
- 要达到的字符串，其长度与 s 相同
- 返回值boolean
- 如果将 s 中的字符一一重命名后得到 t，则为真
约束条件
1 ≤ s.length ≤ 2 × 104t.length == s.lengths和t只包含英文字母和数字。大写和小写是不同的字符。
示例
- 输入
- s = "noon"t = "deed"
- 输出
- true
- 解释
- 将
n重命名为d，并将o重命名为e。每个位置都与这些重命名一致，而且这两个字母有不同的名称。
- 输入
- s = "moon"t = "deed"
- 输出
- false
- 解释
- 从左到右，
m变成d，o变成e，然后n也必须变成d。两个不同的字母不能共用一个名称，所以答案是false。
- 输入
- s = "r2d2"t = "c3p3"
- 输出
- true
- 解释
r变成c，2变成3，d变成p。数字也是字符，两个2都变成3。
进阶
给定一个单词列表，你能否在不逐对比较单词的情况下，把彼此同构的单词分到一组？
提示
逐个打开提示，每个都会多透露一点。
将
s中的字符从左到右逐个位置重命名。之前进行的重命名会在什么时候造成干扰？记录
s中的每个字符变成了t中的哪个字符。这个记录会漏掉一种错误：s中两个不同的字符变成了t中同一个字符。再记录一份从t到s的对应关系，就能发现这种错误。用两个映射同时遍历两个字符串。如果
s[i]和t[i]都还没有映射，就将它们互相映射。否则，它们必须已经互相指向；如果不是，就返回false。
题解
重命名必须是双向对应的：s 中的每个字符都会转换为 t 中的一个字符，而 t 中的每个字符也都来自 s 中的一个字符。使用两个映射，分别表示两个方向，就能在一次遍历中检查这两种对应关系。
比较每一对位置
结果正确，但无法在最大的测试中运行完毕
思路
重命名会让相同的字符保持相同，不同的字符保持不同。因此，对于每一对位置 i 和 j，s[i] == s[j] 必须与 t[i] == t[j] 得出相同的结果。这也足够了：如果每一对都一致，那么把 s 中的每个字符重命名为 t 中对应位置的字符就是定义明确的，而且不会让两个字符得到同一个名称。在 moon 和 deed 中，位置 0 和 3 在 s 中是不同的字母，但在 t 中都是 d，所以答案是 false。
大约有 n²/2 对：当 n = 2 × 10^4 时，如果没有任何一对让循环提前停止，就会进行 2 × 10^8 次比较。
算法
- 遍历每个索引
i，并对每个索引遍历所有更靠后的索引j。 - 判断
s[i]是否等于s[j]，以及t[i]是否等于t[j]。 - 如果两个答案不同，就返回
false。 - 检查完最后一对后，返回
true。
def isIsomorphic(s, t):
n = len(s)
for i in range(n):
for j in range(i + 1, n):
# Two positions must hold equal characters in s exactly when they do in t
if (s[i] == s[j]) != (t[i] == t[j]):
return False
return True两个映射，每个方向一个
思路
阅读字符串时，逐步建立重命名映射。sToT 记录 s 中每个字符变成了什么，tToS 记录 t 中每个字符来自哪里。在位置 i，令 a = s[i] 且 b = t[i]，要么两者都是新字符，你就将它们关联起来；要么它们必须已经互相指向。
只用一个映射是不够的。只用 sToT 时，moon 和 deed 都能通过，因为 s 中没有字母被重命名成两种不同的字符。问题在于 m 和 n 都变成了 d，而在位置 3，tToS 已经记录了 d 来自 m。
每个位置需要进行几次映射操作，因此时间复杂度是 O(n)。每个字符的编码都小于 128，因此每个映射都可以用一个包含 128 个元素的数组实现：空间复杂度为 O(1)。R 和 Swift 版本会先将字符串复制到编码数组中，这需要 O(n) 时间。
算法
- 创建两个空映射，
sToT和tToS。 - 对于每个索引
i，令a = s[i]且b = t[i]。 - 如果
a不在sToT中，且b不在tToS中，则将a映射到b，并将b映射到a。 - 否则，如果
sToT[a]不是b，或者tToS[b]不是a，则返回false。 - 到达最后一个索引后，返回
true。
def isIsomorphic(s, t):
s_to_t = {} # the character of t that each character of s became
t_to_s = {} # the character of s that each character of t came from
for a, b in zip(s, t):
if a not in s_to_t and b not in t_to_s:
s_to_t[a] = b
t_to_s[b] = a
elif s_to_t.get(a) != b or t_to_s.get(b) != a:
return False # a already has another target, or b another source
return True
易错点和边界情况
- 只维护从
s到t的一张映射表。这样会接受moon和deed，也会接受ab和aa。 - 比较每个字符出现的次数。
abcabc和xyzxzy都各有 3 个字符，每个字符出现两次，但第二个b对应的是z，而第一个b对应的是y。 - 把大小写视为相同。
aA包含两个不同的字符，因此无法转换成bb。 - 只为
a到z创建数组映射。大写字母和数字不在这个范围内；应使用 128 个条目，并按完整字符编码进行索引。
常见问题4
同构字符串的时间复杂度是多少？
双映射解法只读取每个位置一次，因此运行时间为 O(n)。映射中每种可能的字符最多保存一项，共有 62 个字母和数字，因此额外空间为 O(1)。比较每一对位置需要 O(n²)。
为什么判断同构字符串需要两个哈希映射？
从 s 到 t 的映射可以发现 s 中的一个字符被映射成了两个不同的字符。但它无法发现 s 中的两个字符被映射成同一个字符的情况，例如 ab 和 aa。从 t 返回 s 的映射可以发现这种情况。
同构具有对称性吗？
是的。一对一重命名可以撤销，因此如果 s 被重命名为 t，将每个名称反向替换，就会把 t 变回 s。isIsomorphic(s, t) 和 isIsomorphic(t, s) 的结果始终一致。
还可以用什么方法检查两个字符串是否同构？
将每个字符替换为它第一次出现的位置，然后比较结果。noon 和 deed 都会变成 0 1 1 0，而 moon 会变成 0 1 1 3。时间复杂度也是 O(n)，两个模式需要 O(n) 的内存。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def isIsomorphic(s, t):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
s = "noon" t = "deed"
预期输出
true