ஐசோமார்பிக் சரங்கள் லீட்கோட் தீர்வு  


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அடோப் அமேசான் ஆப்பிள் ப்ளூம்பெர்க் பேஸ்புக் கூகிள் இன்டெல் லின்க்டு இன் மைக்ரோசாப்ட் ஆரக்கிள் யாகூ
குறியீட்டு ஹாஷ்மேப் பேட்டி நேர்காணல் தயாரிப்பு லீட்கோட் LeetCodeSolutions சரம்

சிக்கல் அறிக்கை  

இந்த சிக்கலில், எங்களுக்கு இரண்டு வழங்கப்படுகிறது சரங்களை, a மற்றும் b. இரண்டு சரங்களும் ஐசோமார்பிக் இல்லையா என்பதைச் சொல்வதே எங்கள் குறிக்கோள்.

கதாபாத்திரங்களின் ஒப்பீட்டு வரிசையை ஒரே மாதிரியாக வைத்திருக்கும் போது, ​​முதல் சரத்தின் எழுத்துக்கள் அதன் நிகழ்வின் அனைத்து புள்ளிகளிலும் (தன்னை உள்ளடக்கியது) எந்த எழுத்தையும் மாற்ற முடியும் என்றால் மட்டுமே இரண்டு சரங்களை ஐசோமார்பிக் என்று அழைக்கிறார்கள். இரண்டு எழுத்துக்களும் ஒரே எழுத்துக்குறியைக் குறிக்க முடியாது.

உதாரணமாக

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

ஐசோமார்பிக் சரங்கள் லீட்கோட் தீர்வு

அணுகுமுறை  

முதல் சரத்தின் ஒவ்வொரு எழுத்துக்கும் மாற்றாக சேமிக்க ஹாஷ்மாப்களைப் பயன்படுத்தலாம். முதல் எழுத்துக்கு மாற்றாக இருக்கும் ஒரு நிலையை நாம் அடைந்தால்,

  • மாற்றீடு மற்ற சரத்தின் எழுத்துக்கு சமமானதா என்பதை நாம் சரிபார்க்கலாம். இல்லையென்றால், சரங்களை ஐசோமார்பிக் ஆக இருக்க முடியாது.
  • முதல் எழுத்துக்கு மாற்றீடு இல்லாதிருந்தால், முதல் சரத்தில் வேறு எந்த எழுத்துக்கும் மாற்றாக இரண்டாவது எழுத்து பயன்படுத்தப்பட்டுள்ளதா என்பதை நாம் சரிபார்க்கலாம். இந்த சோதனை முக்கியமானது, ஏனென்றால் முதல் சரத்தின் ஒவ்வொரு எழுத்தையும் ஒரு தனித்துவமான எழுத்துக்குறி வரைபடமாக்க வேண்டும். இரண்டாவது எழுத்துக்குறி மாற்றப்பட்ட எந்த எழுத்தும் இல்லை என்றால், முதல் எழுத்தின் மாற்றாக இரண்டாவது எழுத்தை ஒதுக்கலாம். இல்லையெனில், சரங்கள் ஐசோமார்பிக் அல்ல.

அல்காரிதம்

  1. துவக்க a பாத்திரம் க்கு பாத்திரம் ஹாஷ்மேப் மாற்று மற்றும் ஒரு பாத்திரம் க்கு பூலியன் ஹாஷ்மேப் பயன்படுத்தப்படும்
  2. சரத்தின் ஒவ்வொரு எழுத்துக்கும் இட்ரேட் s மற்றும் t:
    • If மாற்று கொண்டுள்ளது s [i] ஒரு விசையாக:
      • If மாற்று [கள் [i]]! = t [i]
        • பொய் திரும்பவும்
    • வேறு:
      • If பயன்படுத்தப்பட்டது [t [i]] == உண்மை
        • பொய் திரும்பவும்
      • தொகுப்பு மாற்று [கள் [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), உள்ளீட்டில் நிலையான எழுத்துக்களின் நிலையான எண்ணிக்கை இருக்கும் என்பதால்.