Изоморфни стрингови Решение за леткод  


Ниво на тешкотија Лесно
Често прашувано во Adobe Амазон Јаболко Блумберг Facebook Google Интел Скопје Мајкрософт Oracle Јаху
алгоритми кодирање HashMap интервју интервју подготви LeetCode LeetCodeSolutions Стринг

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

Во овој проблем, ни се дадени две жици, а и б. Нашата цел е да кажеме дали двата жица се изоморфни или не.

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

пример

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

Изоморфни стрингови Решение за леткод

Пристап  

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

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

Алгоритам

  1. Иницијализира а карактер до карактер хашмап замена и карактер до boolean хашмап користат
  2. Повторувам за секој карактер во низата s t:
    • If замена содржи s [i] како клуч:
      • If замена [s [i]]! = t [i]
        • врати лажно
    • Друго:
      • If користено [t [i]] == точно
        • врати лажно
      • постави замена [s [i]] = t [i]
      • постави користено [t [i]] = точно
  3. Врати се вистинито
Видете исто така
Вметнете решение на интервал на леткод

Имплементација на изоморфни низи

Програма C ++

#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;
}

Програма за Java

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

Анализа на комплексноста на растворот на летокод на изоморфни жици

Временска комплексност

О (Н), Н. = должина на жиците s и t.

Комплексноста на просторот 

О (1), бидејќи во влезот ќе има постојан број на уникатни знаци.