ఐసోమార్ఫిక్ స్ట్రింగ్స్ లీట్‌కోడ్ సొల్యూషన్


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది Adobe అమెజాన్ ఆపిల్ బ్లూమ్బెర్గ్ <span style="font-family: Mandali; ">ఫేస్‌బుక్ </span> గూగుల్ ఇంటెల్ లింక్డ్ఇన్ మైక్రోసాఫ్ట్ ఒరాకిల్ యాహూ
హాష్ మ్యాప్ స్ట్రింగ్

సమస్యల నివేదిక

ఈ సమస్యలో, మాకు రెండు ఇవ్వబడ్డాయి తీగలను, a మరియు బి. రెండు తీగలను ఐసోమార్ఫిక్ కాదా అని చెప్పడం మా లక్ష్యం.

అక్షరాల సాపేక్ష క్రమాన్ని ఒకే విధంగా ఉంచేటప్పుడు, మొదటి స్ట్రింగ్‌లోని అక్షరాలను దాని సంభవించిన అన్ని పాయింట్ల వద్ద ఏదైనా అక్షరంతో (దానితో సహా) భర్తీ చేయగలిగితే మాత్రమే రెండు తీగలను ఐసోమార్ఫిక్ అంటారు. రెండు అక్షరాలు ఒకే అక్షరానికి మ్యాప్ చేయలేవు.

ఉదాహరణ

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

ఐసోమార్ఫిక్ స్ట్రింగ్స్ లీట్‌కోడ్ సొల్యూషన్

అప్రోచ్

మొదటి స్ట్రింగ్‌లోని ప్రతి అక్షరానికి ప్రత్యామ్నాయాన్ని సేవ్ చేయడానికి మేము హ్యాష్‌మాప్‌లను ఉపయోగించవచ్చు. మొదటి అక్షరానికి ప్రత్యామ్నాయం ఉన్న స్థితికి మేము చేరుకుంటే,

  • పున string స్థాపన ఇతర స్ట్రింగ్‌లోని అక్షరానికి సమానంగా ఉందో లేదో మనం తనిఖీ చేయవచ్చు. కాకపోతే, తీగలను ఐసోమార్ఫిక్ గా ఉండకూడదు.
  • ఒకవేళ మొదటి అక్షరానికి ప్రత్యామ్నాయం లేనట్లయితే, మొదటి అక్షరంలోని ఇతర అక్షరాలకు బదులుగా రెండవ అక్షరం ఉపయోగించబడిందా అని మేము తనిఖీ చేయవచ్చు. ఈ చెక్ ముఖ్యం ఎందుకంటే మొదటి స్ట్రింగ్‌లోని ప్రతి అక్షరాన్ని ప్రత్యేకమైన అక్షరానికి మ్యాప్ చేయాలి. రెండవ అక్షరం స్థానంలో ఏ అక్షరం లేనట్లయితే, మొదటి అక్షరానికి బదులుగా రెండవ అక్షరాన్ని కేటాయించవచ్చు. లేకపోతే, తీగలను ఐసోమార్ఫిక్ కాదు.

అల్గారిథం

  1. ప్రారంభించండి a పాత్ర కు పాత్ర హాష్ మ్యాప్ భర్తీ మరియు ఒక పాత్ర కు బూలియన్ హాష్ మ్యాప్ ఉపయోగించబడిన
  2. స్ట్రింగ్‌లోని ప్రతి అక్షరానికి మళ్ళించండి s మరియు t:
    • If భర్తీ కలిగి s [i] ఒక కీగా:
      • If భర్తీ [s [i]]! = t [i]
        • తప్పుడు తిరిగి
    • లేకపోతే:
      • If ఉపయోగించారు [t [i]] == నిజం
        • తప్పుడు తిరిగి
      • సెట్ భర్తీ [s [i]] = t [i]
      • సెట్ ఉపయోగించారు [t [i]] = నిజం
  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

ఐసోమోర్ఫిక్ స్ట్రింగ్స్ లీట్‌కోడ్ సొల్యూషన్ యొక్క సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

ఓ (ఎన్), ఎన్ = తీగల s మరియు t పొడవు.

అంతరిక్ష సంక్లిష్టత 

ఓ (1), ఇన్పుట్లో స్థిరమైన అక్షరాల సంఖ్య స్థిరంగా ఉంటుంది.