40.同构字符串

题目

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

思路

• “每个出现的字符都应当映射到另一个字符”。代表字符集合 s , t 之间是「满射」。
• “相同字符只能映射到同一个字符上，不同字符不能映射到同一个字符上”。代表字符集合 s , t 之间是「单射」。
• 因此， s 和 t 之间是「双射」，满足一一对应。考虑遍历字符串，使用哈希表 s2t , t2s 分别记录 s→t , t→s 的映射，当发现任意「一对多」的关系时返回 false 即可。

class Solution {
    fun isIsomorphic(s: String, t: String): Boolean {
        if (s.length != t.length) {
            return false
        }

        val s2tHash = HashMap<Char, Char>()
        val t2sHash = HashMap<Char, Char>()

        for (i in s.indices) {
            val a = s[i]
            val b = t[i]

            if (s2tHash.contains(a)) {
                if (s2tHash[a] != b) {
                    return false
                }
            } else {
                s2tHash[a] = b
            }

            if (t2sHash.contains(b)) {
                if (t2sHash[b] != a) {
                    return false
                }
            } else {
                t2sHash[b] = a
            }

        }
        return true
    }
}

class Solution {
    public boolean isIsomorphic(String s, String t) {
        Map<Character, Character> s2t = new HashMap<>(), t2s = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char a = s.charAt(i), b = t.charAt(i);
            // 对于已有映射 a -> s2t[a]，若和当前字符映射 a -> b 不匹配，
            // 说明有一对多的映射关系，则返回 false ；
            // 对于映射 b -> a 也同理
            if (s2t.containsKey(a) && s2t.get(a) != b || 
                t2s.containsKey(b) && t2s.get(b) != a) {
                return false;
            }
            s2t.put(a, b);
            t2s.put(b, a);
        }
        return true;
    }
}

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        s2t = {}
        t2s = {}

        for i in range(len(s)):
            a = s[i]
            b = t[i]

            if (a in s2t and s2t.get(a) != b) or (b in t2s and t2s.get(b) != a):
                return False
            s2t[a] = b
            t2s[b] = a

        return True

复杂度分析:

• 时间复杂度 O(N) : 其中 N 为字符串 s , t 的长度。遍历字符串 s , t 使用线性时间，hashmap 查询操作使用 O(1) 时间。
• 空间复杂度 O(1) : 题目说明 s 和 t 由任意有效的 ASCII 字符组成。由于 ASCII 字符共 128 个，因此 hashmap s2t , t2s 使用 O(128)=O(1) 空间。

• 下一题

• 邮箱 ：charon.chui@gmail.com
• Good Luck!