Изоморфне жице Леетцоде решење  


Ниво тешкоће Лако
Често питани у адобе амазонка јабука Блоомберг фацебоок гоогле интел ЛинкедИн мицрософт пророчанство иахоо
алгоритми шифрирање ХасхМап Интервју интервјупреп ЛеетЦоде ЛеетЦодеСолутионс низ

Изјава о проблему  

У овом проблему су нам дата два струне, а и б. Циљ нам је да утврдимо да ли су два низа изоморфна или не.

Два низа називају се изоморфним онда и само ако знакове у првом низу може заменити било који знак (укључујући и њега самог) у свим тачкама његовог појављивања, а да релативни редослед знакова остане исти. Не могу се два знака пресликати у исти знак.

Пример

s = "abb"  , t = "cdd"
true
s = "Google" , t = "123456"
false

Изоморфне жице Леетцоде решење

Приступ  

Хешмапе можемо користити да сачувамо замену за сваки знак у првом низу. Ако дођемо до положаја где постоји замена за први лик,

  • Можемо проверити да ли је замена иста као знак у другом низу. Ако није, низови не могу бити изоморфни.
  • У случају да не постоји замена за први знак, можемо да проверимо да ли је други знак коришћен као замена за било који други знак у првом низу. Ова провера је важна јер сваки знак у првом низу морамо мапирати у јединствени знак. Ако не постоји знак чија је замена други знак, можемо доделити други знак као замену за први знак. Иначе, низови нису изоморфни.

Алгоритам

  1. Иницијализујте а карактер до карактер хасхмап замена и а карактер до боолеан хасхмап полован
  2. Понављајте за сваки знак у низу s t:
    • If замена цонтаинс с [и] као кључ:
      • If замена [с [и]]! = т [и]
        • ретурн фалсе
    • Остало:
      • If усед [т [и]] == труе
        • ретурн фалсе
      • сет замена [с [и]] = т [и]
      • сет усед [т [и]] = тачно
  3. Повратак истинит
Види такође
Уметните Интервал Леетцоде решење

Примена решења изоморфних жица са Леетцоде решењем

Програм Ц ++

#include <bits/stdc++.h>

using namespace std;

bool isIsomorphic(string s , string t) {
    int n = s.length();

    unordered_map <char , char> replacement;
    unordered_map <char , bool> used;

    for(int i = 0 ; i < n ; i++)
    {
        if(replacement.count(s[i]))
        {
            if(replacement[s[i]] != t[i])
                return false;
        }
        else
        {
            if(used[t[i]])
                return false;
            replacement[s[i]] = t[i];
            used[t[i]] = true;
        }
    }

    return true;
}

int main() {
    string s = "abb" , t = "cdd";
    cout << (isIsomorphic(s , t) ? "true" : "false") << endl;
    return 0;
}

Јава Програм

import java.util.*;

class isomorphic_string {
    public static void main(String args[]) {
        String s = "abb" , t = "cdd";
        System.out.println(isIsomorphic(s , t) ? "true" : "false");
    }

    public static boolean isIsomorphic(String s , String t) {
        HashMap <Character , Character> replacement = new HashMap <>();
        HashMap <Character , Boolean> used = new HashMap <>();

        for(int i = 0 ; i < s.length() ; i++) {
            if(replacement.containsKey(s.charAt(i))) {
                if(replacement.get(s.charAt(i)) != t.charAt(i))
                    return false;
            }
            else {
                if(used.containsKey(t.charAt(i)))
                    return false;
                replacement.put(s.charAt(i) , t.charAt(i));
                used.put(t.charAt(i) , true);
            }
        }

        return true;
    }
}
true

Анализа сложености решења изоморфних жица са Леетцоде-ом

Сложеност времена

О (Н), Н. = дужина низова с и т.

Сложеност простора 

О (1), пошто ће на улазу бити константан број јединствених знакова.