LeetCode 205 同构字符串 Python代码测试用例运行错误排查

核心逻辑缺陷 #

你的代码仅实现了s到t的单向映射校验，缺失t到s的反向映射唯一性校验，违反了同构字符串的双向唯一映射规则，这是测试用例不通过的根本原因。
同构字符串的判定必须同时满足两个条件：

• s中任意相同字符，只能映射到t中同一个固定字符
• t中任意相同字符，只能被s中唯一一个字符映射，不允许两个不同的s字符对应同一个t字符

失败用例执行过程复盘 #

针对输入s = "badc"，t = "baba"，你的代码执行流程如下：

1. i=0，s[0] = 'b'不在映射字典中，存入键值对'b':'b'
2. i=1，s[1] = 'a'不在映射字典中，存入键值对'a':'a'
3. i=2，s[2] = 'd'不在映射字典中，直接存入键值对'd':'b'——此时t中的字符'b'已经被s中的'b'映射过，出现多对一冲突，代码未做拦截
4. i=3，s[3] = 'c'不在映射字典中，直接存入键值对'c':'a'——此时t中的字符'a'已经被s中的'a'映射过，再次出现多对一冲突，代码仍未拦截
5. 循环执行完成后直接返回True，和预期结果False不符

额外边界问题 #

你写的长度判断逻辑存在问题：

• 未优先判断两个字符串长度是否相等，长度不同的字符串必然不可能同构，可直接返回False
• 长度为0的空字符串属于合法输入，两个空字符串互为同构，不应直接返回False

修复后代码（双映射字典实现） #

class Solution(object):
    def isIsomorphic(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        if len(s) != len(t):
            return False
        s_map_t = {}
        t_map_s = {}
        for sc, tc in zip(s, t):
            # 校验s到t的映射一致性
            if sc in s_map_t:
                if s_map_t[sc] != tc:
                    return False
            else:
                # 校验t到s的映射唯一性，避免多对一
                if tc in t_map_s:
                    return False
                s_map_t[sc] = tc
                t_map_s[tc] = sc
        return True

内容的提问来源于stack exchange，提问作者coder1234