Κάντε τη λύση String Great Leetcode


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

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

Στο πρόβλημα "Make The String Great" μια συμβολοσειρά που δίνεται αποτελείται από πεζά και κεφαλαία γράμματα Πρέπει να κάνουμε αυτή τη συμβολοσειρά καλή αφαιρώντας παρακείμενους χαρακτήρες στη συμβολοσειρά που καθιστούν τη συμβολοσειρά κακή.
Μια καλή συμβολοσειρά είναι μια συμβολοσειρά που δεν έχει δύο παρακείμενους χαρακτήρες όπου και οι δύο χαρακτήρες είναι ίδιοι, αλλά σε διαφορετική περίπτωση. Μπορούμε να κάνουμε αυτή τη λειτουργία πολλές φορές για να κάνουμε τη συμβολοσειρά καλή.

Παράδειγμα

s = "leEeetcode"
"leetcode"

Επεξήγηση:

Στο πρώτο βήμα, μπορούμε να επιλέξουμε τα ευρετήρια 1 και 2 ή 2 και 3, και τα δύο θα μειώσουν το "leEeetcode" σε "leetcode".

"abBAcC"
""

Επεξήγηση:

Πιθανά σενάρια είναι:
Κάντε τη λύση String Great Leetcode

Προσέγγιση

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

Γι 'αυτό αυτό που μπορούμε να κάνουμε είναι ότι μπορούμε να επαναλάβουμε από τον πρώτο χαρακτήρα της δεδομένης συμβολοσειράς και να προσθέσουμε τον χαρακτήρα στη συμβολοσειρά αποτελεσμάτων μας έως ότου δεν είναι κακό.
Πριν προσαρμόσουμε τον τρέχοντα χαρακτήρα, θα ελέγξαμε αν η προσθήκη αυτού του χαρακτήρα στη συμβολοσειρά res θα το έκανε κακό ή όχι συγκρίνοντάς τον με τον τελευταίο χαρακτήρα του string string. Εάν η ακέραια διαφορά (ascii) μεταξύ αυτών των δύο χαρακτήρων είναι ίσος με 32 τότε είναι κακός συνδυασμός αλλιώς είναι καλός. Με βάση αυτό θα κάνουμε την ακόλουθη λειτουργία:

  • Εάν η προσθήκη του χαρακτήρα δεν θα κάνει κακό, θα απλώς προσθέσαμε αυτόν τον χαρακτήρα στο res.
  • Διαφορετικά, δεν θα προσθέσουμε και θα καταργήσουμε τον τελευταίο χαρακτήρα της συμβολοσειράς res.

Για τον παραπάνω αλγόριθμο μπορούμε να χρησιμοποιήσουμε σωρός δομή δεδομένων για την προώθηση χαρακτήρα προς το τέλος και την εμφάνιση χαρακτήρα από το τέλος.
Στο C ++ μπορούμε επίσης να χρησιμοποιήσουμε τάξη χορδών ως στοίβα χαρακτήρων και μπορεί να χρησιμοποιήσει λειτουργίες push_back () και pop_back () όπως class stack.

Εκτέλεση

Πρόγραμμα C ++ για το Make The String Great Leetcode Solution

#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"

Πρόγραμμα Java για το Make The String Great Leetcode Solution

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"

Ανάλυση πολυπλοκότητας για τη λύση του String Great Leetcode

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

Επί) : Όπου n είναι το μήκος της συμβολοσειράς εισόδου. Επειδή επαναλαμβάνουμε τη συμβολοσειρά σε έναν μόνο βρόχο. Ως εκ τούτου, η πολυπλοκότητα του χρόνου θα είναι της τάξης του n.

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

Επί) : Χρησιμοποιούμε μια στοίβα για να αποθηκεύσουμε το τελικό μας αποτέλεσμα. Ως εκ τούτου ο χώρος που χρησιμοποιείται θα είναι της τάξης του n, δηλαδή O (n).