සමාවයවික නූල් ලීට්කෝඩ් විසඳුම


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇෙබෝ ඇමේසන් Apple ජංගම දුරකථන බ්ලූම්බර්ග් ෆේස්බුක් ගූගල් ඉන්ටෙල් LinkedIn මයික්රොසොෆ්ට් ඔරකල් යාහූ
හැෂ්මැප් String

ගැටළු ප්රකාශය

මෙම ගැටලුවේදී අපට දෙකක් ලබා දී ඇත නූල්, a සහ b. අපගේ ඉලක්කය වන්නේ නූල් දෙක සමාවයවිකද නැද්ද යන්න පැවසීමයි.

අක්ෂර දෙකක සාපේක්ෂ අනුපිළිවෙල එකම මට්ටමක තබා ගනිමින් පළමු නූල්වල ඇති අක්ෂර ඕනෑම සිදුවීමකින් (එය ඇතුළුව) ප්‍රතිස්ථාපනය කළ හැකි නම් පමණක් නූල් දෙකක් සමාවයවික ලෙස හැඳින්වේ. එකම අක්ෂරයකට අනුරූප දෙකක් සිතියම් ගත කළ නොහැක.

උදාහරණයක්

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

සමාවයවික නූල් ලීට්කෝඩ් විසඳුම

ප්රවේශය

පළමු නූලෙහි සෑම අක්ෂරයක් සඳහාම ආදේශනය සුරැකීමට අපට හැෂ්මැප් භාවිතා කළ හැකිය. පළමු චරිතය සඳහා ආදේශකයක් ඇති ස්ථානයකට අප ළඟා වන්නේ නම්,

  • ප්‍රතිස්ථාපනය අනෙක් නූලෙහි අක්ෂරයට සමාන දැයි අපට පරීක්ෂා කළ හැකිය. එසේ නොවේ නම්, නූල් සමාවයවික විය නොහැක.
  • පළමු අක්‍ෂරය සඳහා ආදේශකයක් නොමැති නම්, පළමු අක්ෂරයේ වෙනත් අක්ෂර වෙනුවට ආදේශකයක් ලෙස දෙවන අක්‍ෂරය භාවිතා කර ඇත්දැයි අපට පරීක්ෂා කළ හැකිය. මෙම චෙක්පත වැදගත් වන්නේ පළමු නූලෙහි ඇති සෑම අක්ෂරයක්ම අද්විතීය අක්ෂරයකට සිතියම් ගත කළ යුතු බැවිනි. දෙවන අක්‍ෂරය ආදේශ කරන චරිතයක් නොමැති නම්, පළමු අක්‍ෂරයේ ආදේශනය ලෙස අපට දෙවන අක්‍ෂරය පැවරිය හැකිය. එසේ නොමැති නම්, නූල් සමාවයවික නොවේ.

ඇල්ගොරිතම

  1. ආරම්භ කරන්න a ස්වභාවය දක්වා ස්වභාවය hashmap ආදේශකයකි සහ ස්වභාවය දක්වා බූලියන් hashmap භාවිතා
  2. නූලෙහි සෑම අක්ෂරයක් සඳහාම අනුකරණය කරන්න s සහ t:
    • If ආදේශකයකි අඩංගු වේ s [i] යතුරක් ලෙස:
      • 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

සමාවයවික නූල් ලීට්කෝඩ් විසඳුමේ සංකීර්ණතා විශ්ලේෂණය

කාල සංකීර්ණත්වය

ඕ (එන්), එන් = s සහ t නූල් වල දිග.

අභ්‍යවකාශ සංකීර්ණතාව 

ඕ (1), ආදානයේ නියත අද්විතීය අක්ෂර සංඛ්‍යාවක් ඇති බැවින්.