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

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

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

Дмитрий Зверев

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

Сергей Голицын

Senior Java Developer в Covalent Inc. и преподаватель. Больше семи лет в Java-разработке. В свободное время судит хакатоны и делится опытом с начинающими программистами. Пишет статьи для «Хабра» и Medium. Ведёт телеграм-каналы «Полезные ссылки около Java» и Cracking code interview.

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

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

Ввод и вывод. Пример 1

Ввод: s = "egg", t = "add"
Вывод: true

Ввод и вывод. Пример 2

Ввод: s = "foo", t = "bar"
Вывод: false

Ввод и вывод. Пример 3

Ввод: 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;
  }