理解同构字符串算法

Question

我理解以下代码,以查找字符串是否是同构的.该代码使用两个散列s_dict和t_dict分别.我假设字符串长度相同.

def isIsomorphic(s, t):
    s_dict = {}
    t_dict = {}
    for i in range(len(s)):
        if s[i] in s_dict.keys() and s_dict[s[i]] != t[i]:
            return False
        if t[i] in t_dict.keys() and t_dict[t[i]] != s[i]:
            return False
        s_dict[s[i]] = t[i]
        t_dict[t[i]] = s[i]
    return True

现在,如果我修改上面的代码,只使用一个哈希s_dict(),那么它也会给我有限的测试用例提供所需的结果.修改后的代码如下:

def isIsomorphic(s, t):
    s_dict = {}
    for i in range(len(s)):
        if s[i] in s_dict.keys() and s_dict[s[i]] != t[i]:
            return False
        s_dict[s[i]] = t[i]
    return True

上述修改代码失败的测试用例是什么？我对同构字符串的理解是错误的吗？

Answer 1

一个简单的例子,你的代码不适用于s ='ab',t ='aa'.

基本上你必须有两种同构的方式.您的代码只检查了可以从s修改t,但不是相反.