LeetCode: 205. Isomorphic Strings - Simple

题目

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 * 104
• t.length == s.length
• s 和 t 由任意有效的 ASCII 字符组成

解题思路1

• 直接利用indexfunction to compare the relative position of two arrays.

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

运行结果

解题思路2

• Use the idea of ​​a hash table to solve the problem.
• We need to maintain two hash tables,The first hash table starts with sThe characters in are keys,映射到tThe characters in are numeric values;The second hash table starts with tThe characters in are keys,映射到sThe characters in are numeric values,Both hash tables are continuously updated,until a conflict arises,返回错误.
• Format of the specific conflict：If the character corresponding to the current subscript already exists,But not the same as the previous mapping.（The previous mapping can be either the mapping in the first hash table or the mapping in the second hash table）.
• In layman's terms, we have already stored this character when we updated the hash table before,Then when we traverse to this character again, we find that it is different from the previously stored value,就产生了冲突,返回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

运行结果