একটি স্ট্রিং লেটকোড সমাধানের বিপরীত স্বরগুলি


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

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

এই সমস্যায় ক স্ট্রিং দেওয়া হয়েছে এবং আমাদের কেবল এই স্ট্রিংয়ের স্বরগুলি উল্টাতে হবে।

উদাহরণ

"hello"
"holle"

ব্যাখ্যা:
বিপরীত হওয়ার আগে: "এইচello"
বিপরীত পরে: "এইচolle"

"leetcode"
"leotcede"

ব্যাখ্যা:
একটি স্ট্রিং লেটকোড সমাধানের বিপরীত স্বরগুলি

পন্থা 1 (ব্যবহার করে) গাদা)

আমাদের কেবল ইনপুট স্ট্রিংয়ে উপস্থিত স্বরগুলি বিপরীত করতে হবে। সুতরাং আমরা বাম থেকে ডানে একই ক্রমে সমস্ত স্বরগুলি একটি স্ট্যাকে সঞ্চয় করতে পারি। তারপরে আবার আমরা স্ট্রিংটি অতিক্রম করতে পারি এবং প্রতিটি স্বর চরিত্রের জন্য বাম থেকে ডানে আমরা স্ট্যাকের শীর্ষতম মান দিয়ে প্রতিস্থাপন করব।

অ্যালগরিদম

  • একটি সেট মধ্যে সমস্ত স্বর অক্ষর সংরক্ষণ করুন।
  • একটি স্ট্যাক তৈরি করুন এবং ইনপুট স্ট্রিংয়ে উপস্থিত সমস্ত স্বর অক্ষর বাম থেকে ডানে চাপুন।
  • এখন আবার প্রতিটি অক্ষরের জন্য স্ট্রিং অতিক্রম করুন। যদি বর্তমানের অক্ষর স্বর হয় তবে এটিকে স্ট্যাকের শীর্ষতম অক্ষর (ইনপুট স্ট্রিংয়ের ডানদিকে স্বর বর্ণ) দিয়ে প্রতিস্থাপন করুন এবং এটিকে স্ট্যাক থেকে সরান।
  • রূপান্তরিত স্ট্রিংটি ফিরিয়ে দিন।

একটি স্ট্রিং লেটকোড সমাধানের বিপরীত স্বরগুলির জন্য বাস্তবায়ন

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

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

string reverseVowels(string s) {

    set<char> vowels={'a','e','i','o','u','A','E','I','O','U'};
    stack<char> stack;
    for(char c:s)
    {
        if(vowels.count(c)) stack.push(c);
    }

    for(char& c:s)
    {
        if(vowels.count(c)) 
        {
            c=stack.top();
            stack.pop();
        }
    }

    return s;
}

int main() 
{
    string s="leetcode";
    cout<< reverseVowels(s)<<endl;
   
   return 0; 
}
leotcede

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

import java.util.*;

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

        char[] arr= s.toCharArray();

        Set<Character> vowels=new HashSet<Character>();
        vowels.add('a');
        vowels.add('e');
        vowels.add('i');
        vowels.add('o');
        vowels.add('u');
        vowels.add('A');
        vowels.add('E');
        vowels.add('I');
        vowels.add('O');
        vowels.add('U');

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

        for(char c:arr)
        {
            if(vowels.contains(c)) stack.push(c);
        }

        for(int i=0;i<arr.length;i++)
        {
            if(vowels.contains(arr[i])) 
            {
                arr[i]=stack.pop();
            }
        }

        return new String(arr);
    }
    
    public static void main(String args[])
    {
        String s="leetcode";
        System.out.println(reverseVowels(s));
        
    }
}
leotcede

একটি স্ট্রিং লেটকোড সমাধানের বিপরীত স্বরগুলির জন্য জটিলতা বিশ্লেষণ

সময় জটিলতা

চালু): আমরা মাত্র দু'বার স্ট্রিংটি অতিক্রম করেছি। এছাড়াও স্ট্যাকের উপর ধাক্কা এবং পপ অপারেশনটিতে ধ্রুবক সময় লাগে এবং স্বরবর্ণের সেটগুলিতে কেবলমাত্র 10 টি উপাদান থাকে (যেমন এটি একটি চরিত্র সন্ধান করতে ধ্রুব সময় নেয়), সুতরাং সময়ের জটিলতা হ'ল (এন)।

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

চালু): সবচেয়ে খারাপ স্ট্যাকের ইনপুট স্ট্রিংয়ের সমস্ত অক্ষর থাকতে পারে। সুতরাং স্থান জটিলতা হ'ল (এন)।

অ্যাপ্রোচ 2 (দুটি পয়েন্টার ব্যবহার করে একক পাস)

আমরা অ্যালগোরিদম অনুসরণ করে দুটি পয়েন্টার ব্যবহার করে একক পাসে স্বরগুলিও বিপরীত করতে পারি:

  • দুটি ভেরিয়েবল তৈরি করুন শুরু এবং শেষ যথাক্রমে বাম এবং ডান থেকে স্বরগুলিকে নির্দেশ করার জন্য।
  • সূচনা হিসাবে শুরু= 0 এবং শেষ= দৈর্ঘ্য (স্ট্রিং) -1।
  • এখন একটি লুপ চালান শুরু.
  • এই লুপের অভ্যন্তরে এই দুটি পয়েন্টারগুলি সরানোর জন্য দুটি লুপ চালান এবং যথাক্রমে বাম থেকে ডান এবং ডান থেকে বামে যথাক্রমে যাতে তারা পরবর্তী স্বরটির দিকে নির্দেশ করে।
  • শুরু এবং শেষ দ্বারা নির্দেশিত দুটি স্বর অক্ষরকে আদান প্রদান করুন।
  • বৃদ্ধি শুরু এবং হ্রাস শেষ 1 দ্বারা.
  • যখন নতুন স্ট্রিংটি ফেরত দিন শুরু আরও বড় হয় শেষ.

একটি স্ট্রিং লেটকোড সমাধানের বিপরীত স্বরগুলির জন্য বাস্তবায়ন

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

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

string reverseVowels(string s) {

    set<char> vowels={'a','e','i','o','u','A','E','I','O','U'};

    int start=0,end=s.length()-1;
    while(start<end)
    {
        while(start<end && !vowels.count(s[start])) start++;

        while(start<end && !vowels.count(s[end])) end--;

        char temp=s[start];
        s[start]=s[end];
        s[end]=temp;

        start++;
        end--;
    }

    return s;
}

int main() 
{
    string s="leetcode";
    cout<< reverseVowels(s)<<endl;
   
   return 0; 
}
leotcede

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

import java.util.*;

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

       char[] arr= s.toCharArray();
        
        Set<Character> vowels=new HashSet<Character>();
        vowels.add('a');
        vowels.add('e');
        vowels.add('i');
        vowels.add('o');
        vowels.add('u');
        vowels.add('A');
        vowels.add('E');
        vowels.add('I');
        vowels.add('O');
        vowels.add('U');
        
       int start=0,end=arr.length-1;
        while(start<end)
        {
            while(start<end && !vowels.contains(arr[start])) start++;
            
            while(start<end && !vowels.contains(arr[end])) end--;
            
            char temp=arr[start];
            arr[start]=arr[end];
            arr[end]=temp;
            
            start++;
            end--;
        }
        
        return new String(arr);
    }
    
    public static void main(String args[])
    {
        String s="leetcode";
        System.out.println(reverseVowels(s));
        
    }
}
leotcede

একটি স্ট্রিং লেটকোড সমাধানের বিপরীত স্বরগুলির জন্য জটিলতা বিশ্লেষণ

সময় জটিলতা

চালু): স্ট্রিংয়ের প্রতিটি চরিত্র কেবল একবার দেখা হয়েছে, সুতরাং সময়ের জটিলতা হ'ল (এন)।

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

ও (1): স্বরবর্ণের সেট ব্যতীত কোনও অতিরিক্ত স্থান ব্যবহার করা হয় না যেখানে কেবল 10 টি উপাদান রয়েছে (যেমন ধ্রুবক স্থান)। সুতরাং স্থান জটিলতা হ'ল (1)।