स्ट्रिंग लीटकोड सोल्यूशनचे उलट स्वर  


अडचण पातळी सोपे
वारंवार विचारले ऍमेझॉन फेसबुक Google
अल्गोरिदम कोडिंग मुलाखत मुलाखतीची तयारी लेटकोड LeetCodeSolutions अक्षरमाळा दोन पॉईंटर्स

समस्या विधान  

या समस्येमध्ये ए स्ट्रिंग दिले गेले आहे आणि आम्हाला या स्ट्रिंगच्या फक्त स्वरांना उलट करावे लागेल.

उदाहरण

"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 घटक असतात (म्हणजेच ते पात्र शोधण्यात स्थिर वेळ घेईल), म्हणून वेळ जटिलता ओ (एन) असते.

हे सुद्धा पहा
दोन क्रमवारीबद्ध याद्या लीटकोड सोल्यूशन्स विलीन करा

स्पेस कॉम्प्लेक्सिटी 

ओ (एन): सर्वात वाईट स्टॅकमध्ये इनपुट स्ट्रिंगची सर्व अक्षरे असू शकतात. म्हणून अवकाश जटिलता हे ओ (एन) आहे.

अ‍ॅप्रोच २ (दोन पॉईंटर्स वापरुन सिंगल पास)  

आम्ही अल्गोरिदमचे अनुसरण करून दोन पॉईंटर्स वापरुन सिंगल पासमधील स्वर देखील उलट करू शकतो.

  • दोन व्हेरिएबल्स तयार करा प्रारंभ आणि शेवट अनुक्रमे डावीकडून आणि उजवीकडे स्वराकडे लक्ष वेधण्यासाठी
  • म्हणून आरंभ करा प्रारंभ= 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

स्ट्रिंग लीटकोड सोल्यूशनच्या उलट स्वरांसाठी जटिल विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन): स्ट्रिंगच्या प्रत्येक पात्राला फक्त एकदाच भेट दिली जाते, म्हणून वेळ जटिलता ओ (एन) असते.

हे सुद्धा पहा
स्ट्रिंग लीटकोड सोल्यूशनमध्ये वाढती घट

स्पेस कॉम्प्लेक्सिटी 

ओ (1): केवळ 10 घटक (म्हणजेच निरंतर जागा) असलेल्या स्वरांच्या संचाशिवाय अतिरिक्त जागा वापरली जात नाही. म्हणून अवकाश जटिलता ओ (1) आहे.