Αντίστροφα φωνήεντα μιας συμβολοσειράς Leetcode Solution


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις αμαζόνα Facebook Google
κορδόνι Δύο δείκτες

Δήλωση προβλήματος

Σε αυτό το πρόβλημα α κορδόνι δίνεται και πρέπει να αντιστρέψουμε μόνο τα φωνήεντα αυτής της συμβολοσειράς.

Παράδειγμα

"hello"
"holle"

Επεξήγηση:
πριν από την αντιστροφή: «hello"
μετά την αντιστροφή: «holle"

"leetcode"
"leotcede"

Επεξήγηση:
Αντίστροφα φωνήεντα μιας συμβολοσειράς Leetcode Solution

Προσέγγιση 1 (Χρήση Στοίβα)

Πρέπει απλώς να αντιστρέψουμε τα φωνήεντα που υπάρχουν στη συμβολοσειρά εισόδου. Έτσι μπορούμε να αποθηκεύσουμε όλα τα φωνήεντα σε μια στοίβα με την ίδια σειρά από αριστερά προς τα δεξιά. Και πάλι μπορούμε να διασχίσουμε τη συμβολοσειρά και για κάθε χαρακτήρα φωνήεντος από αριστερά προς τα δεξιά θα την αντικαταστήσουμε με την ανώτατη τιμή της στοίβας.

Αλγόριθμος

  • Αποθηκεύστε όλους τους χαρακτήρες φωνήεντος σε ένα σύνολο.
  • Δημιουργήστε μια στοίβα και πιέστε όλους τους χαρακτήρες φωνήεντος που υπάρχουν στη συμβολοσειρά εισόδου από αριστερά προς τα δεξιά.
  • Τώρα διασχίστε ξανά τη συμβολοσειρά για κάθε χαρακτήρα. Εάν ο τρέχων χαρακτήρας είναι φωνήεν, αντικαταστήστε τον με τον κορυφαίο χαρακτήρα της στοίβας (δεξί χαρακτήρας φωνήεντος της συμβολοσειράς εισόδου) και αφαιρέστε τον από τη στοίβα.
  • Επιστρέψτε τη μετατροπή συμβολοσειράς.

Υλοποίηση για Αντίστροφα φωνήεντα μιας συμβολοσειράς Leetcode Solution

Πρόγραμμα 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

Πρόγραμμα Java

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

Ανάλυση πολυπλοκότητας για τα αντίστροφα φωνήεντα μιας συμβολοσειράς Leetcode Solution

Χρόνος πολυπλοκότητας

ΕΠΙ): Περάσαμε τη συμβολοσειρά μόνο δύο φορές. Επίσης, η λειτουργία push και pop στη στοίβα διαρκεί χρόνο και το σύνολο φωνηέντων έχει μόνο 10 στοιχεία (δηλαδή θα χρειαστεί σταθερός χρόνος για την εύρεση ενός χαρακτήρα), επομένως η πολυπλοκότητα του χρόνου είναι O (N).

Διαστημική πολυπλοκότητα 

ΕΠΙ): Στη χειρότερη στοίβα μπορεί να έχει όλους τους χαρακτήρες της συμβολοσειράς εισόδου. Ως εκ τούτου, η πολυπλοκότητα του διαστήματος είναι O (N).

Προσέγγιση 2 (Μονό πέρασμα με δύο δείκτες)

Μπορούμε επίσης να αντιστρέψουμε τα φωνήεντα σε ένα πέρασμα χρησιμοποιώντας δύο δείκτες ακολουθώντας τον αλγόριθμο:

  • Δημιουργήστε δύο μεταβλητές Εκκίνηση τέλος για να δείχνετε φωνήεντα από αριστερά και δεξιά αντίστοιχα.
  • Ξεκινήστε ως Εκκίνηση= 0 και τέλος= μήκος (συμβολοσειρά) -1
  • Τώρα εκτελέστε ένα βρόχο ενώ αρχή.
  • Μέσα σε αυτόν τον βρόχο τρέξτε δύο βρόχους για να μετακινήσετε αυτούς τους δύο δείκτες ξεκινώντας και τελειώνοντας από αριστερά προς δεξιά και δεξιά προς αριστερά αντίστοιχα, έτσι ώστε να δείχνουν στο επόμενο φωνήεν.
  • Ανταλλάξτε τους δύο χαρακτήρες φωνήεντος με την αρχή και το τέλος.
  • Αυξάνουν Εκκίνηση και μείωση τέλος από 1.
  • Επιστρέψτε τη νέα συμβολοσειρά όταν Εκκίνηση γίνεται μεγαλύτερο το τέλος.

Υλοποίηση για Αντίστροφα φωνήεντα μιας συμβολοσειράς Leetcode Solution

Πρόγραμμα 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

Πρόγραμμα Java

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

Ανάλυση πολυπλοκότητας για τα αντίστροφα φωνήεντα μιας συμβολοσειράς Leetcode Solution

Χρόνος πολυπλοκότητας

ΕΠΙ): Κάθε χαρακτήρας της συμβολοσειράς επισκέπτεται μόνο μία φορά, επομένως η πολυπλοκότητα του χρόνου είναι O (N).

Διαστημική πολυπλοκότητα 

O (1): Δεν χρησιμοποιείται επιπλέον χώρος εκτός από το σύνολο των φωνηέντων που έχει μόνο 10 στοιχεία (δηλαδή σταθερό χώρο). Ως εκ τούτου, η πολυπλοκότητα του διαστήματος είναι O (1).