Isomorphic Strings

Q: Зачем нужны две хеш-таблицы для изоморфных строк?

Отображение из s в t обнаруживает ситуацию, когда один символ из s переименован двумя способами. Оно не может обнаружить ситуацию, когда два символа из s переименованы в один и тот же символ, как в ab и aa . Отображение из t обратно в s обнаруживает этот случай.

ЛегкоХеширование

+10

Две строки изоморфны, если можно переименовать символы первой строки, чтобы получить вторую. Каждая копия символа получает одно и то же новое имя, два разных символа никогда не получают одно и то же имя, а символ может сохранить своё имя. Для двух строк s и t одинаковой длины верните true, если они изоморфны, и false, если нет.

Функция

isIsomorphic(s: string, t: string) → boolean

sstring: строка для переименования, буквы и цифры
tstring: строка, до которой нужно дойти, той же длины, что и s
Возвращаетboolean: истинно, если взаимно-однозначное переименование символов s дает t

Ограничения

1 ≤ s.length ≤ 2 × 10⁴
t.length == s.length
s и t содержат только английские буквы и цифры. Заглавные и строчные буквы считаются разными символами.

Примеры

Ввод: s = "noon"t = "deed"
Вывод: true
Пояснение: Переименуй n в d, а o в e. Каждая позиция соответствует этому переименованию, и две буквы получают разные имена.

Ввод: s = "moon"t = "deed"
Вывод: false
Пояснение: Слева направо: m становится d, а o становится e, и тогда n тоже пришлось бы стать d. Две разные буквы не могут иметь одно и то же имя, поэтому ответ — false.

Ввод: s = "r2d2"t = "c3p3"
Вывод: true
Пояснение: r становится c, 2 становится 3, а d становится p. Цифры тоже являются символами, и обе 2 становятся 3.

Дополнительный вопрос

Дан список слов. Можешь ли ты сгруппировать слова, изоморфные друг другу, не сравнивая каждую пару слов?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

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

Сравните каждую пару позиций

Верно, но не успевает на самых больших тестах

Идея

При переименовании одинаковые символы остаются одинаковыми, а разные — разными. Поэтому для каждой пары позиций i и j результат s[i] == s[j] должен совпадать с результатом t[i] == t[j]. Этого также достаточно: если для каждой пары результаты совпадают, переименование каждого символа s в символ t на соответствующих позициях будет корректно определено, и никаким двум символам не будет присвоено одно имя. В moon и deed в позициях 0 и 3 находятся разные буквы в s, но дважды встречается d в t, поэтому ответ — false.

Всего около n²/2 пар: 2 × 10^8 сравнений при n = 2 × 10^4, если ни одна пара не прерывает цикл досрочно.

Алгоритм

Перебери все индексы i, а для каждого из них — все последующие индексы j.
Определи, равно ли s[i] значению s[j] и равно ли t[i] значению t[j].
Если ответы различаются, верни false.
После последней пары верни true.

def isIsomorphic(s, t):
    n = len(s)
    for i in range(n):
        for j in range(i + 1, n):
            # Two positions must hold equal characters in s exactly when they do in t
            if (s[i] == s[j]) != (t[i] == t[j]):
                return False
    return True

Две карты — по одной для каждого направления

Идея

Стройте переименование по мере чтения. В sToT записывается, во что превратился каждый символ s, а в tToS — откуда взялся каждый символ t. В позиции i, где a = s[i] и b = t[i], либо оба символа новые, и вы связываете их, либо они уже должны указывать друг на друга.

Одной карты недостаточно. Если использовать только sToT, пары moon и deed пройдут проверку, потому что ни одна буква s не переименовывается двумя способами. Ошибка в том, что и m, и n превращаются в d, а в позиции 3 в tToS уже записано, что d произошла от m.

Для каждой позиции требуется несколько операций с картой, поэтому время выполнения составляет O(n). Код каждого символа меньше 128, поэтому каждая карта может быть массивом из 128 элементов: пространственная сложность — O(1). Версии на R и Swift сначала копируют строки в массивы кодов, на что требуется O(n).

Алгоритм

Создай две пустые карты: sToT и tToS.
Для каждого индекса i пусть a = s[i], а b = t[i].
Если a нет в sToT и b нет в tToS, сопоставь a с b, а b с a.
Иначе, если sToT[a] не равно b или tToS[b] не равно a, верни false.
После последнего индекса верни true.

def isIsomorphic(s, t):
    s_to_t = {}  # the character of t that each character of s became
    t_to_s = {}  # the character of s that each character of t came from
    for a, b in zip(s, t):
        if a not in s_to_t and b not in t_to_s:
            s_to_t[a] = b
            t_to_s[b] = a
        elif s_to_t.get(a) != b or t_to_s.get(b) != a:
            return False  # a already has another target, or b another source
    return True

Ловушки и крайние случаи

Поддержка одной карты из s в t. Она принимает moon и deed, а также ab и aa.
Сравнение количества вхождений каждого символа. В abcabc и xyzxzy по два раза встречаются три символа, но вхождение b во второй строке находится на месте, соответствующем z, тогда как в первой строке на этом месте находился y.
Считать регистр одинаковым. aA содержит два разных символа, поэтому из него нельзя получить bb.
Выделение массивов карт только для a–z. Заглавные буквы и цифры не попадают в этот диапазон; используйте полный код символа как индекс, выделив 128 элементов.

Частые вопросы4

Какова временная сложность проверки изоморфности строк?

Решение с двумя отображениями просматривает каждую позицию один раз, поэтому работает за O(n). В отображениях хранится не более одной записи для каждого возможного символа — всего 62 буквы и цифры, поэтому дополнительная память составляет O(1). Сравнение каждой пары позиций занимает O(n²).

Зачем нужны две хеш-таблицы для изоморфных строк?

Отображение из s в t обнаруживает ситуацию, когда один символ из s переименован двумя способами. Оно не может обнаружить ситуацию, когда два символа из s переименованы в один и тот же символ, как в ab и aa. Отображение из t обратно в s обнаруживает этот случай.

Симметричен ли изоморфизм?

Да. Переименование один к одному можно отменить, поэтому, если s переименовывается в t, обратная замена каждого имени превращает t обратно в s. isIsomorphic(s, t) и isIsomorphic(t, s) всегда дают одинаковый результат.

Как ещё можно проверить, являются ли две строки изоморфными?

Замените каждый символ позицией его первого появления и сравните результаты. И noon, и deed превращаются в 0 1 1 0, тогда как moon превращается в 0 1 1 3. Это также занимает время O(n) и требует O(n) памяти для двух шаблонов.

def isIsomorphic(s, t):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргументы

s = "noon"
t = "deed"

Ожидаемый вывод

true