План курса / Все задачи / Алгоритмы и структуры данных

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

средне

# решено

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

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

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

Пример 1:

Ввод: s = "abacoo", t = "gogbkk"
Вывод: true

Пример 2:

Ввод: s = "aa", t = "ab"
Вывод: false
Объяснение: буква "a" соответcтвует как символу "a", так и "b"

Пример 3:

Ввод: s = "ab", t = "aa"
Вывод: false
Объяснение: буква "a" соответcтвует как символу "a", так и "b"

Пример 4:

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

Ограничения:

len(s) = len(t)
строки s и t содержат только ascii символы

public class Solution
{
    public static bool IsIsomorphic(string s, string t)
    {
        // sMap: ключ - символ из строки s,
        //  значение - соответствие с символом из строки t
        // tMap: ключ - символ из строки t,
        //  значение - соответствие с символом из строки s
        Dictionary<char, char> sMap = new Dictionary<char, char>();
        Dictionary<char, char> tMap = new Dictionary<char, char>();

        for (int i = 0; i < s.Length; i++)
        {
            // если текущий символ s[i] уже встречался раньше, то
            //  проверяем, что он соответствует тому же символу из
            //  строки t, что и в прошлый раз
            if (sMap.ContainsKey(s[i]) && sMap[s[i]] != t[i])
            {
                return false;
            }
            // аналогичная проверка для строки t необходима, чтобы учесть условие,
            //  что ни один символ не может соответствовать 2-ум разным (даже для строки t)
            if (tMap.ContainsKey(t[i]) && tMap[t[i]] != s[i])
            {
                return false;
            }
            // запоминаем сопоставление символов для строк s и t
            sMap[s[i]] = t[i];
            tMap[t[i]] = s[i];
        }
        return true;
    }
}

#include <string>
#include <unordered_map>

using namespace std;

bool isIsomorphic(const string& s, const string& t) {
    // sMap: ключ - символ из строки s,
    //  значение - соответствие с символом из строки t
    // tMap: ключ - символ из строки t,
    //  значение - соответствие с символом из строки s
    std::unordered_map<char, char> sMap, tMap;
    for (int i = 0; i < s.size(); ++i) {
        // если текущий символ s[i] уже встречался раньше, то
        //  проверяем, что он соответствует тому же символу из
        //  строки t, что и в прошлый раз
        if (sMap.find(s[i]) != sMap.end() && sMap[s[i]] != t[i]) {
            return false;
        }
        // аналогичная проверка для строки t необходима, чтобы учесть условие,
        //  что ни один символ не может соответствовать 2-ум разным (даже для строки t)
        if (tMap.find(t[i]) != tMap.end() && tMap[t[i]] != s[i]) {
            return false;
        }
        // запоминаем сопоставление символов для строк s и t
        sMap[s[i]] = t[i];
        tMap[t[i]] = s[i];
    }
    return true;
}

package main;

func isIsomorphic(s string, t string) bool {
    // sMap: ключ - символ из строки s,
    //  значение - соответствие с символом из строки t
    // tMap: ключ - символ из строки t,
    //  значение - соответствие с символом из строки s
    sMap := make(map[byte]byte)
    tMap := make(map[byte]byte)
    for i := 0; i < len(s); i++ {
        // если текущий символ s[i] уже встречался раньше, то
        //  проверяем, что он соответствует тому же символу из
        //  строки t, что и в прошлый раз
        if val, found := sMap[s[i]]; found && val != t[i] {
            return false
        }
        // аналогичная проверка для строки t необходима, чтобы учесть условие,
        //  что ни один символ не может соответствовать 2-ум разным (даже для строки t)
        if val, found := tMap[t[i]]; found && val != s[i] {
            return false
        }
        // запоминаем сопоставление символов для строк s и t
        sMap[s[i]] = t[i]
        tMap[t[i]] = s[i]
    }
    return true
}

import java.util.*;

public class Solution {
    public boolean isIsomorphic(String s, String t) {
        // sMap: ключ - символ из строки s,
        //  значение - соответствие с символом из строки t
        // tMap: ключ - символ из строки t,
        //  значение - соответствие с символом из строки s
        Map<Character, Character> sMap = new HashMap<>();
        Map<Character, Character> tMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            // если текущий символ s[i] уже встречался раньше, то
            //  проверяем, что он соответствует тому же символу из
            //  строки t, что и в прошлый раз
            if (sMap.containsKey(s.charAt(i)) && sMap.get(s.charAt(i)) != t.charAt(i)) {
                return false;
            }
            // аналогичная проверка для строки t необходима, чтобы учесть условие,
            //  что ни один символ не может соответствовать 2-ум разным (даже для строки t)
            if (tMap.containsKey(t.charAt(i)) && tMap.get(t.charAt(i)) != s.charAt(i)) {
                return false;
            }
            // запоминаем сопоставление символов для строк s и t
            sMap.put(s.charAt(i), t.charAt(i));
            tMap.put(t.charAt(i), s.charAt(i));
        }
        return true;
    }
}

from typing import *

def is_isomorphic(s: str, t: str) -> bool:
    # s_map: ключ - символ из строки s,
    #  значение - соответствие с символом из строки t
    # t_map: ключ - символ из строки t,
    #  значение - соответствие с символом из строки s
    s_map, t_map = {}, {}
    for i in range(len(s)):
        # если текущий символ s[i] уже встречался раньше, то
        #  проверяем, что он соответствует тому же символу из
        #  строки t, что и в прошлый раз
        if s[i] in s_map and s_map[s[i]] != t[i]:
            return False
        # аналогичная проверка для строки t необходима, чтобы учесть условие,
        #  что ни один символ не может соответствовать 2-ум разным (даже для строки t)
        if t[i] in t_map and t_map[t[i]] != s[i]:
            return False
        # запоминаем, сопоставление символов для строк s и t
        s_map[s[i]] = t[i]
        t_map[t[i]] = s[i]
    return True

export function isIsomorphic(s, t) {
    // sMap: ключ - символ из строки s,
    //  значение - соответствие с символом из строки t
    // tMap: ключ - символ из строки t,
    //  значение - соответствие с символом из строки s
    let sMap = {}, tMap = {};

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

Оценка сложности

Время: O(n), где n - длина строки s (длины строк s и t по условия равны)
Память: O(1)

Память оценивается O(1), потому что в строке могут быть только ascii символы (из ограничений условия задачи), а значит число ключей в словаре ограничено константой и оценивается как O(1).