Isomorphic Strings

https://leetcode.com/problems/isomorphic-stringsEasy

Условие

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

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

Примеры

Input: s = "egg", t = "add”

Output: true

Explanation: ‘e’ заменяется на ‘a’, ‘g’ заменяется на ‘d’.
Input: s = "foo", t = "bar”

Output: false

Explanation: Символ ‘o’ нельзя однозначно заменить на два разных символа.
Input: s = "paper", t = "title”

Output: true

Решение

fun isIsomorphic(s: String, t: String): Boolean {
    // Если длины строк не совпадают, они не могут быть изоморфными
    if (s.length != t.length) return false

    // Два мапа для сопоставления символов друг с другом
    val mapS = mutableMapOf<Char, Char>()
    val mapT = mutableMapOf<Char, Char>()

    // Проходим по символам строк
    for (i in s.indices) {
        val charS = s[i]
        val charT = t[i]

        // Проверяем, если символы уже сопоставлены неверно
        if (mapS[charS] != null && mapS[charS] != charT || mapT[charT] != null && mapT[charT] != charS) {
            return false
        }

        // Добавляем соответствие в обе мапы
        mapS[charS] = charT
        mapT[charT] = charS
    }

    return true
}

Временная сложность

O(n), где n — длина строки.

Пространственная сложность

O(n), так как используются два мапа для сопоставления символов.