205. Isomorphic Strings

Задача

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

Две строки s и t являются изоморфными, если символы в s можно заменить, чтобы получить t .

Все вхождения одного символа должны быть заменены на другой символ с сохранением порядка следования символов. Никакие два символа не могут отображаться в один и тот же символ, но символ может отображаться сам в себя.

Решение

Решение

// Временная сложность: O(n). Мы проходим по строке ровно один раз
// Пространственная сложность: O(1). Хотя мы используем дополнительную память для карт, размер этих карт ограничен размером алфавита
 
var isIsomorphic = function(s, t) {
    // Шаг 1: Базовая проверка длины
    // Если длины строк различаются, они не могут быть изоморфны по определению.
    if (s.length !== t.length) return false;
 
    // Шаг 2: Создаем два словаря (Map) для двустороннего отслеживания
    // mapS хранит связь: какой символ из 's' превращается в символ из 't'
    // mapT хранит связь: какой символ из 't' уже занят символом из 's'
    const mapS = new Map();
    const mapT = new Map();
 
    // Шаг 3: Запускаем цикл по всем символам строки
    for (let i = 0; i < s.length; i++) {
        const charS = s[i]; // Текущий символ из первой строки
        const charT = t[i]; // Текущий символ из второй строки
 
        // Шаг 4: Проверяем прямую связь (S -> T)
        // Если мы уже встречали charS раньше...
        if (mapS.has(charS)) {
            // ...проверяем, совпадает ли записанное значение с текущим charT.
            // Если нет (например, 'a' раньше было 'b', а теперь 'a' хочет стать 'c'), возвращаем false.
            if (mapS.get(charS) !== charT) {
                return false;
            }
        }
        // Шаг 5: Проверяем обратную связь (T -> S)
        // Если charS новый, но charT уже использовался для другого символа...
        else {
            if (mapT.has(charT)) {
                // Это значит, что два разных символа из 's' пытаются превратиться в один и тот же 't'.
                // Это запрещено правилами (должна быть биекция).
                return false;
            }
 
            // Шаг 6: Если конфликтов нет, запоминаем новую связь в обе стороны
            mapS.set(charS, charT);
            mapT.set(charT, charS);
        }
    }
 
    // Шаг 7: Если цикл прошел до конца без возврата false, значит строки изоморфны
    return true;
};