理解同构字符串算法

Question

我正在理解下面的代码，以确定字符串是否同构。代码分别使用两个散列s_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()，那么它也会为我有限的测试用例提供所需的结果。修改后的代码如下：

^{pr2}$

以上修改过的代码在哪些情况下会失败？我对同构弦的理解是错误的吗？在

Answer 1

看起来挺有趣的。这里是我使用itertools.groupby的解决方案

from itertools import groupby
from collections import defaultdict

def get_idx_count(word):
    """Turns a word into a series of tuples (idx, consecutive_chars)

    "aabbccaa" -> [[(0, 2), (3, 2)], [(1, 2)], [(2, 2)]]
    """
    lst = defaultdict(list)
    for idx, (grp, val) in enumerate(groupby(word)):
        lst[grp].append((idx, sum(1 for _ in val)))
    return sorted(list(lst.values()))

def is_isomorphic(a, b):
    return get_idx_count(a) == get_idx_count(b)

is_isomorphic('aabbcc', 'bbddcc')  # True
is_isomorphic('aabbaa', 'bbddcc')  # False

我觉得我可以做些更像这样的事情，而不是建立清单：

^{pr2}$

但我还没有机会去测试。然而，它确实有可能提前退出，而不是在最后构建所有的列表并进行比较。它还跳过了一些不需要的排序，只不过我们从dicts中提取，所以bleh。很确定list.sort比保存到collections.OrderedDict快。我想。在

Answer 2

一个简单的例子是，你的代码不能在s='ab'，t='aa'上工作。在

基本上你必须有两种方法才能同构。您的代码只检查t是否可以从s修改，但不能反过来修改。在