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
2
3
4
5
6
7
8
9
10
11

提示：

• 1 <= s.length <= 5 * 104
• t.length == s.length
• s 和 t 由任意有效的 ASCII 字符组成

解题思路1

• 直接利用index函数来进行两个数组相对位置的比较。

Code

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        for i in range(len(s)):
            if s.index(s[i]) != t.index(t[i]):
                return False
        return True
1
2
3
4
5
6

运行结果

解题思路2

• 利用哈希表的思路来进行解题。
• 我们需要维护两个哈希表，第一个哈希表以s中的字符为键，映射到t中的字符为数值；第二个哈希表以t中的字符为键，映射到s中的字符为数值，不断更新两个哈希表，直到出现冲突时，返回错误。
• 具体冲突的格式：如果当前下标对应的字符已经存在，但是与之前的映射不相同。（之前的映射可以是第一个哈希表中的映射或者是第二个哈希表中的映射）。
• 通俗来讲就是我们之前更新哈希表的时候已经存过了这个字符，然后我们再次遍历到这个字符的时候发现与之前存过的数值不一样，就产生了冲突，返回false。

Code

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        hash1 = {}
        hash2 = {}
        for i in range(len(s)):
            if (s[i] in hash1 and hash1[s[i]] != t[i]) or (t[i] in hash2 and hash2[t[i]] != s[i]):
                return False
            hash1[s[i]] = t[i]
            hash2[t[i]] = s[i]
        return True
1
2
3
4
5
6
7
8
9
10

运行结果