आयसोमोर्फिक स्ट्रिंग्स लीटकोड सोल्यूशन  


अडचण पातळी सोपे
वारंवार विचारले अडोब ऍमेझॉन सफरचंद ब्लूमबर्ग फेसबुक Google इंटेल संलग्न मायक्रोसॉफ्ट ओरॅकल याहू
अल्गोरिदम कोडिंग हॅशमॅप मुलाखत मुलाखतीची तयारी लेटकोड LeetCodeSolutions अक्षरमाळा

समस्या विधान  

या समस्येमध्ये, आम्हाला दोन दिले आहेत स्ट्रिंग्स, अ आणि बी. आमचे उद्दीष्ट हे सांगण्यासाठी आहे की दोन्ही तार isomorphic आहेत की नाही.

दोन स्ट्रिंगस आयसोमोर्फिक असे म्हणतात जेव्हा आणि केवळ त्या अक्षराची सापेक्ष क्रम समान ठेवताना पहिल्या स्ट्रिंगमधील वर्ण कोणत्याही वर्णाने (स्वतःच) बदलले जाऊ शकतात. कोणतीही वर्ण दोन समान वर्णांवर नकाशा करु शकत नाही.

उदाहरण

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

आयसोमोर्फिक स्ट्रिंग्स लीटकोड सोल्यूशनपिन

दृष्टीकोन  

पहिल्या स्ट्रिंगमधील प्रत्येक कॅरक्टरची रिप्लेसमेंट सेव्ह करण्यासाठी आम्ही हॅशमॅप्स वापरू शकतो. जर आपण अशा स्थानावर पोहोचलो जिथे पहिल्या वर्णची जागा आहे.

  • बदली इतर स्ट्रिंगमधील अक्षराइतकीच आहे का ते आम्ही तपासू शकतो. नसल्यास, तार isomorphic असू शकत नाहीत.
  • पहिल्या अक्षराची जागा घेण्याऐवजी पहिल्या स्ट्रिंगमधील दुसर्‍या अक्षराच्या बदलीच्या रूपात दुसरे अक्षर वापरले आहे का ते तपासू शकतो. ही तपासणी महत्त्वपूर्ण आहे कारण आम्हाला पहिल्या स्ट्रिंगमधील प्रत्येक पात्राला एका अद्वितीय वर्णात मॅप करणे आवश्यक आहे. ज्याचे रिप्लेसमेंट हे दुसरे कॅरेक्टर असेल असे कोणतेही कॅरेक्टर नसल्यास, आम्ही पहिल्या कॅरेक्टरची रिप्लेसमेंट म्हणून दुसरे कॅरेक्टर देऊ शकतो. अन्यथा, तार isomorphic नाहीत.
हे सुद्धा पहा
अंतराल लीटकोड सोल्यूशन घाला

अल्गोरिदम

  1. आरंभ करणे ए वर्ण ते वर्ण हॅशमॅप बदली आणि एक वर्ण ते बुलियन हॅशमॅप वापरले
  2. स्ट्रिंगमधील प्रत्येक वर्गासाठी Iterate s आणि t:
    • If बदली समाविष्टीत आहे चे [मी] की म्हणून:
      • If पुनर्स्थित [एस [i]]! = टी [i]
        • खोटे परत
    • अन्यथा:
      • If वापरले [टी [i]] == सत्य
        • खोटे परत
      • संच पुनर्स्थित [एस [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), कारण इनपुटमध्ये सतत अनन्य वर्णांची संख्या असेल.

1