পার্থক্যটি লেটকোড সমাধানটি সন্ধান করুন  


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

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

উদাহরণ  

a = "abcde" , b = "ebacdf"
f
a = "aaaa" , b = "aaaaa"
a

ব্যাখ্যা # 1

স্ট্রিংয়ে যুক্ত হওয়া অতিরিক্ত অক্ষর b স্ট্রিং হিসাবে 'f' a এটি ধারণ করে না।

ব্যাখ্যা # 2

স্ট্রিং স্ট্রিংয়ের সময় 4 'a' অক্ষর রয়েছে সুতরাং ৫. অতিরিক্ত অক্ষরটি 'ক'।

পদ্ধতির (বাছাই করা)  

আমরা উভয় স্ট্রিং বাছাই করতে পারি এবং তারপরে তারা উভয়কে পৃথক পৃথক অবস্থানের জন্য অক্ষরে চিঠি দুটি পুনরুক্ত করতে পারি। দ্বিতীয় স্ট্রিংটিতে সর্বদা একটি থাকবে অতিরিক্ত চরিত্র সুতরাং, আমরা সর্বদা একটি পয়েন্ট পাবেন যেখানে স্ট্রিং a এবং b পৃথক। যাইহোক, স্ট্রিং যেখানে একটি কেস হতে পারে b বাছাইয়ের পরে স্ট্রিংয়ের প্রতিটি চরিত্রের সাথে মেলে a ইন কিন্তু শেষ পর্যন্ত একটি অতিরিক্ত চরিত্র আছে। আমাদের এটির একটি বিশেষ কেস পরিচালনা করতে হবে।

পার্থক্যটি লেটকোড সমাধানটি সন্ধান করুনপিন

অ্যালগরিদম

  1. উভয় স্ট্রিং বাছাই করুন, a এবং b। এটি জাভাতে সম্ভব না হওয়ায় আমরা প্রথমে সেগুলিতে রূপান্তর করি চর অ্যারে
  2. সংক্ষিপ্ত স্ট্রিংয়ে উপস্থিত প্রতিটি চরিত্রের জন্য, আমরা চিঠি-পত্র-চিঠি পরীক্ষা করি:
    • যদি স্ট্রিংয়ে অক্ষর থাকে স্ট্রিংয়ের সাথে সম্পর্কিত অক্ষরের সমান নয় b:
      • এই চরিত্রটি ফিরিয়ে দিন
  3. স্ট্রিংয়ের শেষ অক্ষরটি ফিরিয়ে দিন এটি অতিরিক্ত চরিত্র হিসাবে
  4. ফলাফল মুদ্রণ করুন
আরো দেখুন
এমনকি সংখ্যার সংখ্যা সহ লেটকোড সমাধানের সন্ধান করুন

পার্থক্যটি লেটকোড সমাধান আবিষ্কারের বাস্তবায়ন

সি ++ প্রোগ্রাম

#include <bits/stdc++.h>
using namespace std;

char findTheDifference(string a , string b)
{
    sort(a.begin() , a.end());
    sort(b.begin() , b.end());
    int n = a.size();
    for(int i = 0 ; i < n ; i++)
        if(a[i] != b[i])
            return b[i];
    return b[n];
}

int main()
{
    string a = "abcde" , b = "ebacdf";
    cout << findTheDifference(a , b) << '\n';

    return 0;
}

জাভা প্রোগ্রাম

import java.util.Arrays;

class find_the_difference
{
    public static void main(String args[])
    {
        String a = "abcde" , b = "ebacdf";
        System.out.println(findTheDifference(a , b));
    }

    static char findTheDifference(String a , String b)
    {
        char[] a_CharArray = a.toCharArray();
        char[] b_charArray = b.toCharArray();

        Arrays.sort(a_CharArray);
        Arrays.sort(b_charArray);

        int n = a.length();
        for(int i = 0 ; i < n ; i++)
            if(a_CharArray[i] != b_charArray[i])
                return b_charArray[i];
        return b_charArray[n];
    }
}
f

পার্থক্য লেটকোড সমাধানের জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (এনলগএন), যেখানে এন = দীর্ঘ স্ট্রিংয়ের দৈর্ঘ্য। আমরা স্ট্রিংগুলি / চর অ্যারেগুলিকে বাছাই করি যা O (NlogN) সময় নেয়।

স্থান জটিলতা

চালু) জাভা এবং ও (1) সি ++ তে আমরা স্ট্রিংগুলিকে রূপান্তর করি চর অ্যারে জাভাতে

পদ্ধতির (হ্যাশিং)  

উভয় স্ট্রিংয়ে আমরা প্রতিটি অক্ষরকে এর ফ্রিকোয়েন্সি সহ হ্যাশ করতে পারি এবং ফ্রিকোয়েন্সিতে পৃথক পৃথক চরিত্রটি খুঁজে পেতে পারি। যেহেতু আমাদের কাছে অবিচ্ছিন্ন অক্ষর রয়েছে। এই অ্যালগরিদম উপরে আলোচিতগুলির চেয়ে দ্রুত। একটি দক্ষ বাস্তবায়ন হিসাবে, আমরা একটি তৈরি করতে পারি হ্যাশ টেবিল এবং স্ট্রিংয়ের প্রতিটি চরিত্রের জন্য ফ্রিকোয়েন্সি বৃদ্ধি করুন a এবং স্ট্রিংয়ের প্রতিটি চরিত্রের জন্য ফ্রিকোয়েন্সি হ্রাস করুন b. এটি আমাদের এমন এক ক্ষেত্রে ছেড়ে দেবে যেখানে ঠিক একটি চরিত্রের ফ্রিকোয়েন্সি হয় অ-শূন্য এবং এটি স্ট্রিংয়ের অতিরিক্ত অক্ষর হবে b.

অ্যালগরিদম

  1. হিসাবে সমস্ত অক্ষরের ফ্রিকোয়েন্সি সঞ্চয় করতে একটি হ্যাশ টেবিল শুরু করুন ফ্রিকোয়েন্সি
  2. স্ট্রিং প্রতিটি অক্ষরের জন্য a:
    • হ্যাশ টেবিলটিতে এর ফ্রিকোয়েন্সি বৃদ্ধি করুন
  3. স্ট্রিং প্রতিটি অক্ষরের জন্য b:
    • হ্যাশ টেবিল এ তার ফ্রিকোয়েন্সি হ্রাস
    • এর ফ্রিকোয়েন্সি সমান হলে -1:
      • এই চরিত্রটি ফিরিয়ে দিন
  4. ফাংশন সিনট্যাক্স বজায় রাখতে '-' ফেরান
  5. ফলাফল মুদ্রণ করুন
আরো দেখুন
বাইনারি অ্যারেতে প্রশ্নগুলি টগল করুন এবং টগল করুন

পার্থক্যটি লেটকোড সমাধান আবিষ্কারের বাস্তবায়ন

সি ++ প্রোগ্রাম

#include <bits/stdc++.h>
using namespace std;

char findTheDifference(string a , string b)
{
    unordered_map <int , int> frequency;
    for(char &c : a)
        frequency[c]++;
    for(char &c : b)
    {
        frequency[c]--;
        if(frequency[c] == -1)
            return c;
    }
    //this case will never happen
    return '-';
}


int main()
{
    string a = "abcde" , b = "ebacdf";
    cout << findTheDifference(a , b) << '\n';

    return 0;
}

জাভা প্রোগ্রাম

import java.util.*;

class find_the_difference
{
    public static void main(String args[])
    {
        String a = "abcde" , b = "ebacdf";
        System.out.println(findTheDifference(a , b));
    }

    static char findTheDifference(String a , String b)
    {
        HashMap <Character , Integer> frequency = new HashMap<>();
        char x;
        for(int i = 0 ; i < a.length() ; i++)
        {
            x = a.charAt(i);
            frequency.put(x , frequency.getOrDefault(x , 0) + 1);
        }

        for(int i = 0 ; i < b.length() ; i++)
        {
            x = b.charAt(i);
            frequency.put(x , frequency.getOrDefault(x , 0) - 1);
            if(frequency.getOrDefault(x , 0) == -1)
                return x;
        }
        //this case will never occur
        return '-';
    }
}
f

পার্থক্য লেটকোড সমাধানের জটিলতা বিশ্লেষণ

সময় জটিলতা

চালু), দীর্ঘতর স্ট্রিংয়ের এন = আকার, আমরা অক্ষরের ফ্রিকোয়েন্সিগুলি আপডেট করতে একবার উভয় স্ট্রিংয়ের মধ্য দিয়ে যেতে পারি।

স্থান জটিলতা

ও (1)। যদিও আমরা তাদের ফ্রিকোয়েন্সি সহ অক্ষরগুলি সংরক্ষণ করতে একটি হ্যাশটেবল ব্যবহার করি, তবে ইনপুট নির্বিশেষে আমরা ধ্রুবক স্পেস ব্যবহার করি। সুতরাং, স্থান জটিলতা ধ্রুবক।