इसोमोर्फिक स्ट्रिंग्स लेटकोड समाधान


कठिनाई तह सजिलो
बारम्बार सोधिन्छ एडोब अमेजन एप्पल ब्लूमबर्ग फेसबुक गुगल Intel LinkedIn माइक्रोसफ्ट बजेट याहू
हशम्याप घागो

समस्या वक्तव्य

यस समस्यामा हामीलाई दुई दिइयो तार, a र b हाम्रो लक्ष्य भनेको दुई स्ट्रिंगहरू isomorphic हो वा होइन भनेर बताउनु हो।

दुई स्ट्रिंगहरूलाई आइसोमोर्फिक भनिन्छ यदि र यदि केवल पहिलो स्ट्रिंगमा क्यारेक्टरहरूद्वारा प्रतिस्थापन गर्न सकिन्छ (आफै समावेश सहित) सबै घटनाहरूमा वर्णहरूको सापेक्षिक क्रमलाई समान राख्दै। कुनै दुई अक्षरले उही वर्णमा नक्शा गर्न सक्दैन।

उदाहरणका

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

इसोमोर्फिक स्ट्रिंग्स लेटकोड समाधान

दृष्टिकोण

हामी पहिलो स्ट्रिंगमा प्रत्येक चरित्रको लागि प्रतिस्थापन बचत गर्न ह्यासम्याप प्रयोग गर्न सक्छौं। यदि हामी त्यस्तो स्थानमा पुग्छौं जहाँ पहिलो वर्णको प्रतिस्थापन हुन्छ,

  • हामी जाँच गर्न सक्छौं कि प्रतिस्थापन अन्य स्ट्रिंगमा चरित्र जस्तै छ कि छैन। यदि होईन भने, तारहरू isomorphic हुन सक्दैन।
  • यदि त्यहाँ पहिलो क्यारेक्टरको लागि कुनै प्रतिस्थापन छैन भने, हामी जाँच गर्न सक्छौं कि दोस्रो अक्षर पहिलो स्ट्रि inमा अन्य कुनै चरित्रको लागि प्रतिस्थापनको रूपमा प्रयोग गरिएको छ। यो जाँच महत्त्वपूर्ण छ किनकि हामीले पहिलो अक्षरमा प्रत्येक वर्णलाई अद्वितीय वर्णमा नक्सा गर्न आवश्यक पर्दछ। यदि त्यहाँ कुनै चरित्र छैन जसको प्रतिस्थापन दोस्रो अक्षर हो, हामी दोस्रो वर्णलाई पहिलो वर्णको प्रतिस्थापनको रूपमा प्रदान गर्न सक्दछौं। अन्यथा, तारहरू isomorphic छैनन्।

अल्गोरिदम

  1. आरम्भ गर्नुहोस् वर्ण लाई वर्ण ह्यासम्याप प्रतिस्थापन र एक वर्ण लाई बूलियन ह्यासम्याप प्रयोग
  2. स्ट्रि inमा प्रत्येक चरित्रको लागि इटरेट गर्नुहोस् st:
    • 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;
}

जावा कार्यक्रम

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

जटिलता आइसोमोर्फिक स्ट्रिंग्स लेटकोड समाधानको विश्लेषण

समय जटिलता

O (N), N = तार s र t को लम्बाई।

ठाउँ जटिलता 

O (१), किनकि त्यहाँ इनपुटमा अनौंठो वर्णहरूको निरन्तर संख्या हुनेछ।