আইসোমরফিক স্ট্রিংস লেটকোড সলিউশন


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় রৌদ্রপক্ব ইষ্টক মর্দানী স্ত্রীলোক আপেল ব্লুমবার্গ ফেসবুক গুগল ইন্টেল লিঙ্কডইন মাইক্রোসফট আকাশবাণী নরপশু
হ্যাশ মানচিত্র স্ট্রিং

সমস্যা বিবৃতি

এই সমস্যায়, আমাদের দুটি দেওয়া হয় স্ট্রিং, ক এবং খ। আমাদের লক্ষ্যটি দুটি স্ট্রিং isomorphic কিনা তা জানানো।

দুটি স্ট্রিংকে আইসোমর্ফিক বলা হয় যদি এবং কেবল তখনই যদি প্রথম স্ট্রিংয়ের অক্ষরগুলির অক্ষরের আপেক্ষিক ক্রম একই রাখার সাথে সাথে তার উপস্থিতির সমস্ত পয়েন্টগুলিতে (নিজেই অন্তর্ভুক্ত) কোনও অক্ষর দ্বারা প্রতিস্থাপন করা যায়। কোনও দুটি চরিত্র একই চরিত্রের মানচিত্র করতে পারে না।

উদাহরণ

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

আইসোমরফিক স্ট্রিংস লেটকোড সলিউশন

অভিগমন

আমরা প্রথম স্ট্রিংয়ের প্রতিটি অক্ষরের প্রতিস্থাপন সংরক্ষণ করতে হ্যাশম্যাপ ব্যবহার করতে পারি। যদি আমরা এমন কোনও জায়গায় পৌঁছে যাই যেখানে প্রথম অক্ষরের প্রতিস্থাপন রয়েছে,

  • প্রতিস্থাপনটি অন্যান্য স্ট্রিংয়ের অক্ষরের মতো একই কিনা তা আমরা পরীক্ষা করতে পারি। যদি তা না হয় তবে স্ট্রিংগুলি আইসোমর্ফিক হতে পারে না।
  • প্রথম চরিত্রের জন্য কোনও প্রতিস্থাপন না থাকলে, আমরা প্রথম অক্ষরে অন্য কোনও চরিত্রের প্রতিস্থাপন হিসাবে দ্বিতীয় অক্ষরটি ব্যবহার করা হয়েছে কিনা তা আমরা পরীক্ষা করতে পারি। এই চেকটি গুরুত্বপূর্ণ কারণ আমাদের প্রথম স্ট্রিংয়ের প্রতিটি চরিত্রকে একটি অনন্য চরিত্রের মানচিত্র তৈরি করতে হবে। যদি এমন কোনও অক্ষর উপস্থিত না থাকে যার প্রতিস্থাপন দ্বিতীয় অক্ষর হয় তবে আমরা দ্বিতীয় অক্ষরটিকে প্রথম অক্ষরের প্রতিস্থাপন হিসাবে নির্ধারণ করতে পারি। অন্যথায়, স্ট্রিংগুলি isomorphic নয়।

অ্যালগরিদম

  1. সূচনা a চরিত্র থেকে চরিত্র হ্যাশ মানচিত্র প্রতিস্থাপন এবং একটি চরিত্র থেকে বুলিয়ান হ্যাশ মানচিত্র ব্যবহৃত
  2. স্ট্রিংয়ের প্রতিটি চরিত্রের জন্য Iterate s এবং t:
    • If প্রতিস্থাপন ধারণ এস [আমি] একটি কী হিসাবে:
      • If প্রতিস্থাপন [এস [আমি]]! = টি [আমি]
        • মিথ্যা প্রত্যাবর্তন
    • অন্য:
      • If ব্যবহৃত [t [i]] == সত্য
        • মিথ্যা প্রত্যাবর্তন
      • সেট প্রতিস্থাপন [এস [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

আইসমোরফিক স্ট্রিংস লেটকোড সলিউশন এর জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (এন), এন = এর স্ট্রিং এর দৈর্ঘ্য এবং টি।

স্পেস জটিলতা ity 

ও (1), যেহেতু ইনপুটটিতে ধারাবাহিকভাবে অনন্য অক্ষর থাকবে।