স্ট্রিংকে গ্রেট লেটকোড সলিউশন করুন  


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

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

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

উদাহরণ

s = "leEeetcode"
"leetcode"

ব্যাখ্যা:

প্রথম পদক্ষেপে, আমরা সূচক 1 এবং 2 বা 2 এবং 3 চয়ন করতে পারি, উভয়ই "লিটকোড" "লিটকোড" এ হ্রাস করবে।

"abBAcC"
""

ব্যাখ্যা:

সম্ভাব্য পরিস্থিতিগুলি হ'ল:
স্ট্রিংকে গ্রেট লেটকোড সলিউশন করুন

অভিগমন  

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

এর জন্য আমরা যা করতে পারি তা হ'ল আমরা প্রদত্ত স্ট্রিংয়ের প্রথম অক্ষরটি পুনরাবৃত্তি করতে পারি এবং অক্ষরটিকে আমাদের ফলাফলের স্ট্রিংয়ের সাথে যুক্ত করতে পারি যতক্ষণ না এটি খারাপ নয়।
বর্তমান চরিত্রটি সংযোজন করার আগে আমরা পরীক্ষা করব যে রেস স্ট্রিংয়ে এই চরিত্রটি যুক্ত করা খারাপ রেজাল্ট করবে কিনা তা রেস স্ট্রিংয়ের শেষ চরিত্রের সাথে তুলনা করে। অবিচ্ছেদ্য পার্থক্য হলে (ASCII) এই দুটি অক্ষরের মধ্যে 32 এর সমান হয় তবে এটি খারাপ সংমিশ্রণ হয় অন্যথায় এটি ভাল। তার ভিত্তিতে আমরা নিম্নলিখিত অপারেশন করব:

  • চরিত্রটি সংযোজন খারাপ না হলে, আমরা কেবল সেই চরিত্রটিকে বিশ্রামে যুক্ত করতে পারি।
  • অন্যথায়, আমরা সংযোজন করব না এবং রেজ স্ট্রিংয়ের শেষ অক্ষরটি সরিয়ে দেব।
আরো দেখুন
একটি নম্বরকে হেক্সাডেসিমাল লেটকোড সমাধানে রূপান্তর করুন

উপরের অ্যালগরিদমের জন্য আমরা ব্যবহার করতে পারি গাদা অক্ষরটি শেষের দিকে ধাক্কা দেওয়ার জন্য এবং শেষ থেকে চরিত্রটি বের করার জন্য ডেটা কাঠামো।
সি ++ তে আমরাও ব্যবহার করতে পারি স্ট্রিং ক্লাস অক্ষরের স্ট্যাক হিসাবে এবং স্ট্যাক ক্লাসের মতো পুশ_ব্যাক () এবং পপব্যাক () ক্রিয়াকলাপ ব্যবহার করতে পারে।

বাস্তবায়ন  

স্ট্রিং গ্রেট লেটকোড সলিউশন তৈরির জন্য সি ++ প্রোগ্রাম

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

string makeGood(string s) {

    string goodString;

    for(char ch:s)
    {
        if((!goodString.empty()) && abs(goodString.back()-ch)==32)  
            goodString.pop_back();
        else  
            goodString.push_back(ch);
    }

    return goodString;
}

int main() 
{
    string s = "leEeetcode";
    
    cout<<makeGood(s)<<endl;

  return 0; 
}
"leetcode"

স্ট্রিং গ্রেট লেটকোড সলিউশন তৈরির জন্য জাভা প্রোগ্রাম

import java.lang.*;
import java.util.*;

class Rextester
{  
    public static String makeGood(String s) {

        Stack<Character> stack= new Stack<Character>();

        for(int i=0;i<s.length();i++)
        {
            if((!stack.isEmpty()) && Math.abs(stack.peek()-s.charAt(i))==32 )
                stack.pop();
            else
                stack.push(s.charAt(i));
        }

        char res[]= new char[stack.size()];
        
        for(int i=res.length-1;i>=0;i--) 
            res[i]= stack.pop();

        return new String(res);

    }
    
    public static void main(String args[])
    {
        String s = "leEeetcode";

        System.out.println(makeGood(s));
        
    }
}
"leetcode"

স্ট্রিং গ্রেট লেটকোড সলিউশন তৈরির জন্য জটিলতা বিশ্লেষণ  

সময় জটিলতা

চালু) : যেখানে এন ইনপুট স্ট্রিংয়ের দৈর্ঘ্য। কারণ আমরা একক লুপে স্ট্রিংটির মাধ্যমে পুনরাবৃত্তি করছি। অতএব সময় জটিলতা অর্ডার করা হবে।

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

চালু) : আমরা আমাদের চূড়ান্ত ফলাফল সঞ্চয় করতে একটি স্ট্যাক ব্যবহার করছি। সুতরাং ব্যবহৃত স্থান হ'ল n এর অর্ডার হবে, অর্থাৎ ও (এন)।