اسومورفڪ اسٽرنگس ليٽ ڪوڊ جو حل


تڪليف جي سطح آسان
بار بار پڇڻ ۾ ايڊوب Amazon ايپل Bloomberg ڪريو گوگل اڳوڻن LinkedIn، Microsoft جي Oracle ياهو
هش ميپ اسٽرنگ

مسئلي جو بيان

انهي مسئلي ۾ ، اسان ٻه ڏنل آهيون پودا، ا ۽ ب. اسان جو مقصد اهو ٻڌائڻ آهي ته ڇا ٻه تار isomorphic آهن يا نه.

ٻن اسٽرنگس کي اسومورفڪ چئبو آهي جيڪڏهن صرف ۽ صرف جيڪڏهن پهريون وار واري شڪل ۾ ڪردار کي ڪنهن به ڪردار سان تبديل ڪري سگهجي (بشمول پنهنجو پاڻ) ان جي واقعيت جي سڀني نقطن تي جڏهن ڪردارن جي لاڳيتي نظم کي ساڳيو ئي رکڻ گهرجي. ٻه اکر ساڳيا ڪردار نقشي نٿا ڏين.

مثال

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

اسومورفڪ اسٽرنگس ليٽ ڪوڊ جو حل

چرچو

اسان پهرين اکرن ۾ هر ڪردار جي متبادل کي بچائڻ لاءِ هشميپ استعمال ڪري سگهون ٿا. جيڪڏهن اسان هڪ پوزيشن تي پهچي جتي پهرين ڪردار جو متبادل آهي ،

  • اسان چڪاس ڪري سگھون ٿا ته متبادل ٻئي سٽرنگ ۾ ساڳي آھي جيتري شڪل. جيڪڏهن نه ، واري تار isomorphic نٿي ٿي سگهي.
  • ان صورت ۾ جيڪڏهن پهرين ڪردار جو متبادل نه هجي ، اسان جاچ ڪري سگهنداسين ته پهريون ڪردار پهريون ڪردار ۾ ڪنهن ٻئي ڪردار جي متبادل طور استعمال ڪيو ويو آهي. اهو چيڪ ضروري آهي ڇاڪاڻ ته اسان کي پهرين اکرن ۾ هر ڪردار کي منفرد ڪردار جي نقشي ڏيڻ جي ضرورت آهي. جيڪڏهن ڪوبه ڪردار ناهي جنهن جو متبادل ٻئي ڪردار آهي ، اسين ٻئي ڪردار کي بدلائي سگهون ٿا پهرين ڪردار جي جاءِ تي. ٻي صورت ۾ ، تار صحيح نه آهي.

الورورٿم

  1. شروعاتي اي شخصيت جي طرف شخصيت هيش ميپ متبادل ۽ هڪ شخصيت جي طرف بوليان هيش ميپ استعمال شده
  2. تار ۾ هر ڪردار جي لاءِ ورجاءُ s ۽ t:
    • If متبادل تي مشتمل آهي ايس [مان] چاٻي وانگر
      • 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

آئومورفڪ اسٽرنگس ليٽڪوڊ حل جي پيچيدگي تجزيه

وقت جي پيچيدگي

اي (اين) ، اين = تارن جي ڊيگهه ۽ ٽي.

خلائي پيچيدگي 

اي (1) ، جيئن ته انپٽ ۾ منفرد نمبرن جو مستقل نمبر هوندو.