Изоморфные строки (Isomorphic Strings)

Условие

Изоморфные строки (Isomorphic Strings)

Условие Даны две строки s и t одинаковой длины. Определите, являются ли они изоморфными.

Две строки изоморфны, если существует взаимно-однозначное соответствие между символами первой строки и символами второй: каждый символ из s всегда заменяется на один и тот же символ из t, и при этом два разных символа из s не могут заменяться на один и тот же символ из t.

Входные данные Две строки s и t, состоящие из строчных латинских букв.

Выходные данные true, если строки изоморфны, иначе false.

Ограничения

• 1 <= s.length == t.length <= 10^4
• Строки содержат только строчные латинские буквы

def is_isomorphic(s, t): # TODO: напишите решение здесь return False

Ответ

Ведите два отображения: символ s в символ t и обратно. Если уже установленное соответствие противоречит очередной паре, строки не изоморфны.

def is_isomorphic(s, t):
    if len(s) != len(t):
        return False
    forward, backward = {}, {}
    for left, right in zip(s, t):
        if left in forward and forward[left] != right:
            return False
        if right in backward and backward[right] != left:
            return False
        forward[left] = right
        backward[right] = left
    return True

Первый словарь гарантирует постоянную замену каждого исходного символа, второй запрещает слияние двух разных символов в один. Например, egg и add подходят, а ab и aa — нет. Время O(n), память O(k); для заданного алфавита k не превышает 26.