Изоморфные строки

Даны две строки.

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

Например, "paper" и "title" — изоморфные строки. Источник.

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

Решение

Половина дела в этой задаче — очень точно сформулировать что значит «изоморфность». Замечания про относительный порядок и взаимно однозначное соответствие могут и не прозвучать в явном виде, важно их уточнить самостоятельно.

Далее пробуем такое соответствие составить на основе двух строк и будем следить, что указанные выше инварианты не нарушаются.

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isIsomorphic = function(s, t) {
		// если длина строк разная — таблица соответствия разваливается,
		// в колонках не может быть разное количество строк
    if (s.length !== t.length) {
        return false;
    }
		
		// таблица соответствия символов их строки s в строку t
		//(s2t — значит s to 2)
    const s2t = new Map();
		// будем так же следить за тем какие символы из t уже были использованы,
		// чтобы проверять взаимно однозначное соответствие
    const usedT = new Set();
	  
		// бежим по строке, последовательно обрабатывая каждый символ,
		// тем самым сохраняем относительный порядок
    for (let i = 0; i < s.length; i++) {
				// если такой ключ уже есть:
				// проверим что в строке t в этом месте нужный символ,
				// иначе табличка развалится
        if (s2t.has(s[i])) {
            if (s2t.get(s[i]) !== t[i]) {
                return false;                   
            }
        } else {
						// если такого ключа нет, прежде чем создать новую запись,
						// проверим, что символ в строке t ещё не использовался.
						//(рассмотрите такой тест: s = "ab", t = "aa")
            if (usedT.has(t[i])) {
                return false;
            }
						// добавляем новую запись в табличку,
						// и текущий символ строки t в сет, как «использованный»
            s2t.set(s[i], t[i]);
            usedT.add(t[i]);
        }
    }
    return true;
};

Вместо Map и Set можно использовать два массива фиксированной длины. Хотя, по сути, решение остаётся таким же: пробегаемся по строке и пробуем построить взаимно однозначное соответствие.

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isIsomorphic = function(s, t) {
	// В интервал [0 .. 255] влезают все простые символы.
	// Про алфавит стоит уточнить у интервьюера.
	const m1 = new Array(256).fill(-1);
	// -1 → условно «значение ещё не определено»
	const m2 = new Array(256).fill(-1);

	for (let i = 0; i < s.length; i++) {
		// либо значение не определено (-1),
		// либо значение определено раньше и должно совпадать,
		// иначе взаимно однозначное соответствие не установить
		if (m1[s.charCodeAt(i)] !== m2[t.charCodeAt(i)]) {
			return false;
		}
		// назначим соответствующим символам из строк s и t одно и то же значение:
		// удобно использовать для этого индекс, хотя может быть что угодно,
		// главное, чтобы значения были разными для разных символов
		// и одинаковыми для одинаковых
		m1[s.charCodeAt(i)] = i;
		m2[t.charCodeAt(i)] = i;
	}
	return true;
}

Важно отметить, что сложность по памяти O(m), где m — размер алфавита. В данном случае известно, что m = 256 , поэтому сложность константная. От длины строк размер дополнительной памяти не зависит.

✈️ Телеграм-канал — https://t.me/coding_interviews