Isomorphic Strings
Задача: даны две строки S и T. Необходимо определить, изоморфны ли они.
Справка: строки S и T изоморфны, если символы в S можно заменить, чтобы получить T. То есть все вхождения символа необходимо заменить другим символом с сохранением порядка символов. Никакие два символа не могут соответствовать одному и тому же символу, но символ может соответствовать самому себе.
Входные данные: S, T — строки, содержащие только ASCII символы. Размер строк от 1 до 10⁴.
Вывод: true / false
Примеры:
- S = “egg”, T = “add”
Output: true - S = “foo”, T = “bar”
Output: false
Разбор
Для решения этой задачи можно воспользоваться двумя хэш-таблицами, 1я будет хранить соответствие букв по 1му слову, 2я таблица — по 2му слову.
То есть на i-м шаге мы запоминаем, что s[i] символу соот-т символ t[i] и наооборот. Если на следующих шагах мы встретим любое не соот-ве по уже записанным данным из хэш-таблиц, то строки s и t не являются изоморфными.
Также очевидно, что строки с разной длиной не являются изоморфными.
Реализация
https://gist.github.com/unilecs/54fa46780495e876fed48ecd822853f5