આઇસોમોર્ફિક સ્ટ્રીંગ્સ લીટકોડ સોલ્યુશન


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એડોબ એમેઝોન સફરજન બ્લૂમબર્ગ ફેસબુક Google ઇન્ટેલ LinkedIn માઈક્રોસોફ્ટ ઓરેકલ યાહૂ
હેશમેપ શબ્દમાળા

સમસ્યા નિવેદન

આ સમસ્યામાં, અમને બે આપવામાં આવે છે શબ્દમાળાઓ, એ અને બી. અમારું ધ્યેય એ કહેવાનું છે કે બે શબ્દમાળા isomorphic છે કે નહીં.

બે શબ્દમાળાઓને આઇસોમોર્ફિક કહેવામાં આવે છે જો અને ફક્ત ત્યારે જ જો પ્રથમ શબ્દમાળાના પાત્રોને તેના અક્ષરના સંબંધિત ક્રમમાં સમાન રાખીને તેની ઘટનાના તમામ બિંદુઓ પર (પોતાને સહિત) બદલી શકાય છે. કોઈ પણ બે અક્ષરો સમાન પાત્રને નકશા કરી શકતા નથી.

ઉદાહરણ

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

આઇસોમોર્ફિક સ્ટ્રીંગ્સ લીટકોડ સોલ્યુશન

અભિગમ

આપણે પહેલા શબ્દમાળાના દરેક પાત્રની બદલીને બચાવવા માટે હેશમેપ્સનો ઉપયોગ કરી શકીએ છીએ. જો આપણે એવી સ્થિતિએ પહોંચીએ કે જ્યાં પહેલા પાત્રની બદલી હોય,

  • અમે ચકાસી શકીએ છીએ કે રિપ્લેસમેન્ટ અન્ય શબ્દમાળાના પાત્ર જેવું જ છે કે નહીં. જો નહીં, તો શબ્દમાળાઓ આઇસોમોર્ફિક હોઈ શકતા નથી.
  • જો પહેલા પાત્ર માટે કોઈ રિપ્લેસમેન્ટ ન હોય તો, અમે તપાસ કરી શકીએ કે પહેલા અક્ષરમાં બીજા અક્ષરના સ્થાને બીજા અક્ષરનો ઉપયોગ કરવામાં આવ્યો છે કે નહીં. આ તપાસ મહત્વપૂર્ણ છે કારણ કે આપણે પહેલા અક્ષરના દરેક પાત્રને અનન્ય પાત્રમાં નકશા બનાવવાની જરૂર છે. જો કોઈ પાત્ર અસ્તિત્વમાં ન હોય જેનું રિપ્લેસમેન્ટ બીજું પાત્ર છે, તો આપણે બીજા પાત્રને પ્રથમ પાત્રના સ્થાને તરીકે સોંપી શકીએ છીએ. નહિંતર, શબ્દમાળાઓ isomorphic નથી.

અલ્ગોરિધમ

  1. પ્રારંભ કરો એ પાત્ર થી પાત્ર હેશમેપ રિપ્લેસમેન્ટ અને પાત્ર થી બુલિયન હેશમેપ વપરાયેલ
  2. શબ્દમાળા દરેક પાત્ર માટે અલગ s અને t:
    • If રિપ્લેસમેન્ટ સમાવે s [i] કી તરીકે:
      • If રિપ્લેસમેન્ટ [s [i]]! = t [i]
        • ખોટા પાછા
    • બાકી:
      • If વપરાયેલ [ટી [i]] == સાચું
        • ખોટા પાછા
      • સમૂહ રિપ્લેસમેન્ટ [s [i]] = t [i]
      • સમૂહ વપરાયેલ [ટી [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

આઇસોમોર્ફિક સ્ટ્રિંગ્સ લીટકોડ સોલ્યુશનનું જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન), એન શબ્દમાળાઓની લંબાઈ = અને ટી.

અવકાશ જટિલતા 

ઓ (1), કારણ કે ઇનપુટમાં અનન્ય અક્ષરોની સતત સંખ્યા રહેશે.