ഐസോമോഫിക് സ്ട്രിംഗ്സ് ലീറ്റ്കോഡ് പരിഹാരം


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു അഡോബി ആമസോൺ ആപ്പിൾ ബ്ലൂംബർഗ് ഫേസ്ബുക്ക് ഗൂഗിൾ ഇന്റൽ ലിങ്ക്ഡ് മൈക്രോസോഫ്റ്റ് ഒറാക്കിൾ യാഹൂ
ഹാഷ്‌മാപ്പ് സ്ട്രിംഗ്

പ്രശ്നം പ്രസ്താവന

ഈ പ്രശ്‌നത്തിൽ, ഞങ്ങൾക്ക് രണ്ട് നൽകിയിരിക്കുന്നു സ്ട്രിംഗുകൾ, എ, ബി. രണ്ട് സ്ട്രിംഗുകളും ഐസോമോഫിക് ആണോ അല്ലയോ എന്ന് പറയുക എന്നതാണ് ഞങ്ങളുടെ ലക്ഷ്യം.

പ്രതീകങ്ങളുടെ ആപേക്ഷിക ക്രമം അതേപടി നിലനിർത്തിക്കൊണ്ട്, ആദ്യത്തെ സ്ട്രിംഗിലെ പ്രതീകങ്ങൾ അതിന്റെ എല്ലാ ഘട്ടങ്ങളിലും (സ്വയം ഉൾപ്പെടെ) ഏതെങ്കിലും പ്രതീകം ഉപയോഗിച്ച് മാറ്റിസ്ഥാപിക്കാൻ കഴിയുമെങ്കിൽ മാത്രമേ രണ്ട് സ്ട്രിംഗുകളെ ഐസോമോഫിക് എന്ന് വിളിക്കൂ. രണ്ട് പ്രതീകങ്ങൾക്കും ഒരേ പ്രതീകത്തിലേക്ക് മാപ്പ് ചെയ്യാൻ കഴിയില്ല.

ഉദാഹരണം

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

ഐസോമോഫിക് സ്ട്രിംഗ്സ് ലീറ്റ്കോഡ് പരിഹാരം

സമീപനം

ആദ്യ സ്ട്രിംഗിലെ ഓരോ പ്രതീകത്തിനും പകരംവയ്ക്കൽ സംരക്ഷിക്കാൻ ഞങ്ങൾക്ക് ഹാഷ്മാപ്പുകൾ ഉപയോഗിക്കാം. ആദ്യ പ്രതീകത്തിന് പകരമുള്ള ഒരു സ്ഥാനത്ത് ഞങ്ങൾ എത്തിയാൽ,

  • മാറ്റിസ്ഥാപിക്കൽ മറ്റ് സ്‌ട്രിംഗിലെ പ്രതീകത്തിന് തുല്യമാണോ എന്ന് ഞങ്ങൾക്ക് പരിശോധിക്കാം. ഇല്ലെങ്കിൽ, സ്ട്രിംഗുകൾ ഐസോമോഫിക് ആകാൻ കഴിയില്ല.
  • ആദ്യ പ്രതീകത്തിന് പകരക്കാരനില്ലെങ്കിൽ, ആദ്യ സ്‌ട്രിംഗിലെ മറ്റേതൊരു പ്രതീകത്തിനും പകരമായി രണ്ടാമത്തെ പ്രതീകം ഉപയോഗിച്ചിട്ടുണ്ടോ എന്ന് ഞങ്ങൾക്ക് പരിശോധിക്കാം. ഈ പരിശോധന പ്രധാനമാണ്, കാരണം ആദ്യത്തെ സ്ട്രിംഗിലെ എല്ലാ പ്രതീകങ്ങളും ഒരു അദ്വിതീയ പ്രതീകത്തിലേക്ക് മാപ്പ് ചെയ്യേണ്ടതുണ്ട്. രണ്ടാമത്തെ പ്രതീകത്തിന്റെ പകരക്കാരനായി ഒരു പ്രതീകവും നിലവിലില്ലെങ്കിൽ, ആദ്യ പ്രതീകത്തിന്റെ പകരമായി നമുക്ക് രണ്ടാമത്തെ പ്രതീകം നൽകാം. അല്ലെങ്കിൽ, സ്ട്രിംഗുകൾ ഐസോമോഫിക് അല്ല.

അൽഗോരിതം

  1. ആരംഭിക്കുക a പ്രതീകം ലേക്ക് പ്രതീകം ഹാഷ്‌മാപ്പ് മാറ്റിസ്ഥാപിക്കുക ഒരു പ്രതീകം ലേക്ക് ബൂളിയൻ ഹാഷ്‌മാപ്പ് ഉപയോഗിച്ച
  2. സ്‌ട്രിംഗിലെ ഓരോ പ്രതീകത്തിനും ആവർത്തിക്കുക s ഒപ്പം t:
    • If മാറ്റിസ്ഥാപിക്കുക അടങ്ങിയിരിക്കുന്നു s [i] ഒരു കീയായി:
      • If മാറ്റിസ്ഥാപിക്കൽ [s [i]]! = t [i]
        • തെറ്റായി മടങ്ങുക
    • അല്ലെങ്കിൽ:
      • If ഉപയോഗിച്ചു [t [i]] == true
        • തെറ്റായി മടങ്ങുക
      • ഗണം മാറ്റിസ്ഥാപിക്കൽ [s [i]] = t [i]
      • ഗണം ഉപയോഗിച്ചു [t [i]] = true
  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

ഐസോമോഫിക് സ്ട്രിംഗുകളുടെ സങ്കീർണ്ണ വിശകലനം ലീറ്റ്കോഡ് പരിഹാരം

സമയ സങ്കീർണ്ണത

O (N), N. = സ്ട്രിംഗുകളുടെ ദൈർഘ്യം s, t.

ബഹിരാകാശ സങ്കീർണ്ണത 

O (1), ഇൻ‌പുട്ടിൽ‌ സ്ഥിരമായ അദ്വിതീയ പ്രതീകങ്ങൾ‌ ഉണ്ടായിരിക്കും.