Задача: проверить строки на изоморфность
2026-02-21 19:58 Diff
https://skillbox.ru/media/code/zadacha-proverit-stroki-na-izomorfnost/

#статьи

  • 1 сен 2022
  • 0

Задача: проверить строки на изоморфность

Решаем задачи, которые дают программистам на собеседованиях в IT-компаниях. Сегодня проверяем строки на изоморфность.

Иллюстрация: Polina Vari для Skillbox Media

Любитель научной фантастики и технологического прогресса. Хорошо сочетает в себе заумного технаря и утончённого гуманитария. Пишет про IT и радуется этому.

Условие. Даны две строки — s и t. Нужно проверить их изоморфность.

Пояснение: строки s и t называются изоморфными, если все вхождения каждого символа строки s можно последовательно заменить другим символом и получить строку t. Порядок символов при этом должен сохраняться, а замена — быть уникальной. Так, два разных символа строки s нельзя заменить одним и тем же символом из строки t, а вот одинаковые символы в строке s должны заменяться одним и тем же символом. Звучит сложно, поэтому просто посмотрите примеры ввода и вывода :)

Ввод: s = "egg", t = "add" Вывод: trueВвод: s = "foo", t = "bar" Вывод: falseВвод: s = "paper", t = "title" Вывод: true

Решить эту задачу самостоятельно и на разных языках программирования можно на LeetCode. Наше решение взято из Telegram-канала Сергея Cracking code interview.

Решение

Чтобы решить эту задачу, нам нужно создать два массива. Каждый массив мы будем использовать как словарь со всеми возможными символами, которые находятся в ASCII-таблице. Так мы сократим количество вариантов всего до 256 символов и упростим задачу. А вот если бы мы решали её, используя кодировку Unicode, нам бы понадобился массив побольше.

Массивы нужны, чтобы сопоставлять символы из одной строки с символами из другой. Алгоритм работает так:

  • Сначала мы создаём два массива и заполняем все элементы значением «–1». Это нужно, чтобы в будущем понять, где у нас незанятые элементы.
  • Проходим по символам внутри строк и превращаем каждый символ в ASCII-код — число от 0 до 255. На каждой итерации у нас будет по два таких числа: для строки s и t.
  • Затем проверяем, что коды этих символов не заняты в обоих массивах. Если это так, то записываем в первый массив код символа строки t, а во второй — код символа строки s.
  • Если один из элементов массива уже занят кодом, значит, строки не будут изоморфными.

Вот как этот алгоритм будет реализован на Java:

public boolean isIsomorphic(String s, String t) { int[] sChar = new int[256]; int[] tChar = new int[256]; Arrays.fill(sChar, -1); Arrays.fill(tChar, -1); for(int i = 0; i < s.length(); i++){ int sCharIdx = s.charAt(i); int stCharIdx = t.charAt(i); if (sChar[sCharIdx] == -1 && tChar[stCharIdx] == -1){ sChar[sCharIdx] = stCharIdx; tChar[stCharIdx] = sCharIdx; } else if (sChar[sCharIdx] != stCharIdx || tChar[stCharIdx] != sCharIdx) { return false; } } return true; }

Результаты

Временная сложность: O(n) — так как мы перебирали все элементы массива.

Ёмкостная сложность: O(1) — нам нужно определённое количество места в памяти: для двух строк и для двух массивов с символами по 256 байт.

Научитесь: Профессия Java-разработчик + ИИ Узнать больше