205. 同构字符串 Easy

给定两个字符串 s 和 t ，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

示例 1：
输入：s = "egg", t = "add"
输出：true

示例 2：
输入：s = "foo", t = "bar"
输出：false

示例 3：
输入：s = "paper", t = "title"
输出：true

解题思路

输入：两个字符串 s 和 t

输出：判断是否同构

本题属于 哈希表 问题。

用两个哈希表 key_cache val_cache 记录 key -> val 以及 val -> key

以 s 为 key，t 为 val

遍历字符串 s

• 判断 key 在 key_cache 时跟 t 对应的字符是否一致
• 判断 val 在 val_cache 时跟 s 对应的字符是否一致

然后记录在对应的哈希表中

都判断正确则返回正确

代码实现

python

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        # 长度不同，不可能同构
        if len(s) != len(t):
            return False

        # 两个字典：分别记录 s->t 和 t->s 的映射关系
        key_cache = {}  # s 中字符映射到 t 中字符
        val_cache = {}  # t 中字符映射到 s 中字符

        for i in range(len(s)):
            key = s[i]  # s 中当前位置的字符
            val = t[i]  # t 中当前位置的字符

            # 如果 s 中字符已出现过，但映射的字符和当前 val 不一致，冲突
            if key in key_cache and key_cache[key] != val:
                return False
            
            # 如果 t 中字符已出现过，但映射的字符和当前 key 不一致，冲突
            if val in val_cache and val_cache[val] != key:
                return False

            # 建立/更新双向映射关系
            key_cache[key] = val
            val_cache[val] = key
        
        # 遍历完成没有冲突，则是同构字符串
        return True

javascript

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isIsomorphic = function(s, t) {
    if (s.length !== t.length) return false;

    const keyCache = {};
    const valCache = {};

    for (let i = 0; i < s.length; i++) {
        const key = s[i];
        const val = t[i];

        if (keyCache[key] && keyCache[key] !== val) return false;
        if (valCache[val] && valCache[val] !== key) return false;

        keyCache[key] = val;
        valCache[val] = key;
    }

    return true;
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

链接

205 国际版

205 中文版