स्ट्रि Le लेटकोड समाधानको रिभर्स स्वरहरू


कठिनाई तह सजिलो
बारम्बार सोधिन्छ अमेजन फेसबुक गुगल
घागो दुई पोइन्टरहरू

समस्या वक्तव्य

यो समस्यामा string दिइएको छ र हामीले यस स्ट्रि ofको स्वरहरू मात्र उल्टाउनु पर्छ।

उदाहरणका

"hello"
"holle"

व्याख्या:
उल्टाउनु अघि: "hello"
उल्टो पछाडि: "holle"

"leetcode"
"leotcede"

व्याख्या:
स्ट्रि Le लेटकोड समाधानको रिभर्स स्वरहरू

दृष्टिकोण १ (प्रयोग गर्दै थाक)

हामीले भर्खर इनपुट स्ट्रि inमा उपस्थित स्वरहरू उल्टाउनु पर्छ। त्यसैले हामी स्ट्याकमा बायाँ देखि दायाँ सबै स्वरहरू भण्डार गर्न सक्छौं। फेरी हामी स्ट्रि tra ट्र्याभ गर्न सक्दछौं र प्रत्येक स्वर वर्णको लागि बायाँ देखि दायाँ हामी त्यसलाई स्ट्याकको माथिल्लो मानको साथ बदल्छौं।

अल्गोरिदम

  • सेटमा सबै स्वर वर्णहरू भण्डार गर्नुहोस्।
  • एक स्ट्याक सिर्जना गर्नुहोस् र इनपुट स्ट्रिंगमा बायाँ देखि दायाँमा रहेका सबै स्वर वर्णहरू पुश गर्नुहोस्।
  • अब फेरी प्रत्येक चरित्र को लागी स्ट्रि tra। यदि हालको चरित्र स्वर हो भने, यसलाई स्ट्याकको माथिल्लो चरित्र (इनपुट स्ट्रि ofको दायाँ स्वर वर्ण) सँग बदल्नुहोस् र यसलाई स्ट्याकबाट हटाउनुहोस्।
  • रूपान्तरित स्ट्रि Return फिर्ता गर्नुहोस्।

स्ट्रिंग लेटकोड समाधानको रिभर्स स्वरहरूको लागि कार्यान्वयन

C ++ कार्यक्रम

#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

स्ट्रिity लेटकोड समाधानको रिभर्स स्वरको लागि जटिलता विश्लेषण

समय जटिलता

O (N): हामीले दुई पटक मात्र स्ट्रिंग गर्नुभयो। स्ट्याकमा पनि पुश र पप अपरेशनमा स्थिर समय लिन्छ र स्वरहरूको सेटमा केवल १० तत्वहरू हुन्छन् (उदाहरणका लागि यसले चरित्र खोज्नको लागि स्थिर समय लिन्छ), त्यसैले समय जटिलता ओ (एन) हो।

ठाउँ जटिलता 

O (N): सबैभन्दा नराम्रो स्ट्याकमा इनपुट स्ट्रि ofको सबै क्यारेक्टरहरू हुन सक्छन्। त्यसैले अन्तरिक्ष जटिलता O (N) हो।

दृष्टिकोण २ (दुई पोइन्टर्स प्रयोग गरेर एकल पास)

हामी एल्गोरिथ्मलाई अनुसरण गरेर दुई पोइन्टर्सको प्रयोग गरेर एकल पासमा स्वर पनि उल्टाउन सक्दछौं।

  • दुई भेरिएबलहरू सिर्जना गर्नुहोस् सुरुअन्त बायाँ र दायाँ बाट क्रमशः स्वरमा औंल्याउनको लागि।
  • को रूपमा आरम्भ सुरु= ० र अन्त= लम्बाई (स्ट्रिंग) -१।
  • अब एक लूप चलाउनुहोस् सुरु गर्नुहोस्.
  • यस लूप भित्र यी दुई पोइन्टरहरू सुरू गर्न र अन्त्य क्रमश: बायाँबाट दायाँ र दायाँ देखि बायाँ क्रमशः दुई लूपहरू चलाउनुहोस् जसले गर्दा उनीहरूले अर्को स्वरमा औंल्याउँछन्।
  • सुरु र अन्तबाट दर्साइएको दुई स्वर वर्णहरू साटासाट गर्नुहोस्।
  • बढ्नु सुरु र कम अन्त 1 द्वारा।
  • नयाँ स्ट्रिंग फिर्ता गर्नुहोस् जब सुरु ठूलो हुन्छ अन्त।

स्ट्रिंग लेटकोड समाधानको रिभर्स स्वरहरूको लागि कार्यान्वयन

C ++ कार्यक्रम

#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 लेटकोड समाधानको रिभर्स स्वरको लागि जटिलता विश्लेषण

समय जटिलता

O (N): स्ट्रि ofको प्रत्येक चरित्र एक पटक मात्र भ्रमण गरिन्छ, त्यसकारण समय जटिलता O (N) हो।

ठाउँ जटिलता 

O (१): कुनै थप स्पेस प्रयोग हुँदैन स्वरको सेट बाहेक केवल १० तत्वहरू हुन्छन् (जस्तै स्थिर स्थान)। त्यसैले अन्तरिक्ष जटिलता ओ (१) हो।