Αναδιάταξη χώρων μεταξύ λέξεων Λύση κωδικού Leetcode


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

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

Σε αυτό το πρόβλημα, μας δίνεται ένα κείμενο κορδόνι έχοντας έναν αριθμό λέξεων που τοποθετούνται ανάμεσα στα κενά. Οι λέξεις μπορούν να έχουν μόνο πεζά αγγλικά γράμματα. Φυσικά κάθε λέξη χωρίζεται με τουλάχιστον ένα κενό. Επίσης, το κείμενο έχει τουλάχιστον μία λέξη.
π.χ. κείμενο = "η πρακτική κάνει τέλεια"
Όπως μπορούμε να δούμε, υπάρχει αυθαίρετος αριθμός κενών.
Πρέπει να μετατρέψουμε ένα κείμενο σε μια τέτοια μορφή στην οποία υπάρχει ίσος αριθμός κενών μεταξύ κάθε λέξης και αν παραμείνει κάποιο κενό, τότε αυτά θα συγκεντρωθούν μετά την τελευταία λέξη.
Δεν χρειάζεται να αλλάξουμε τον συνολικό αριθμό κενών. Επίσης, η ακολουθία των λέξεων δεν πρέπει να αλλάξει.

Παράδειγμα

text = " practice makes perfect"
"practice makes perfect "

Επεξήγηση:

Αναδιάταξη χώρων μεταξύ λέξεων Λύση κωδικού Leetcode

Έχει 7 κενά και 3 λέξεις.
Θα διαιρέσουμε εξίσου τα 7 διαστήματα ώστε να ταιριάζουν στα κενά 3-1 = 2 μεταξύ των λέξεων. Έτσι, στην έξοδο μας θα έχουμε 7/2 = 3 κενά μεταξύ των λέξεων και 7-6 = 1 υπολειπόμενο διάστημα θα συσσωρευτεί μετά την τελευταία λέξη.
Επομένως η παραγωγή θα ήταν «η πρακτική κάνει τέλεια».

text = " this is a sentence "
"this is a sentence"

Επεξήγηση:

Υπάρχουν συνολικά 9 κενά και 4 λέξεις. Μπορούμε να διαιρέσουμε ομοιόμορφα τα 9 κενά μεταξύ των λέξεων: 9 / (4-1) = 3 κενά.

Προσέγγιση

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

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

Ας υποθέσουμε ότι εάν υπάρχουν λέξεις n, τότε οι θέσεις μεταξύ των λέξεων είναι n-1.
Έτσι, πρέπει να χωρίσουμε τα κενά (ας μετρήσουμε) σε αυτά τα n-1 μέρη
Ως εκ τούτου, το πάτωμα (μέτρηση / n-1) θα είναι το πλάτος των διαστημάτων που θα διαχωρίζουν όλες τις λέξεις.
και ο υπόλοιπος αριθμός κενών θα προστεθεί μετά την τελευταία λέξη.
δηλαδή το πλήθος% (n-1) θα είναι ο υπόλοιπος αριθμός κενών.

Τέλος, θα συνεχίσουμε να προσθέτουμε κάθε λέξη και τον κατώτατο αριθμό (μέτρηση / n-1) αριθμός διαστημάτων μεταξύ κάθε ζεύγους λέξεων και τον αριθμό% (n-1) του αριθμού κενών μετά την τελευταία λέξη και θα επιστρέψουμε την τελική συμβολοσειρά.

Εκτέλεση

Πρόγραμμα C ++ Αναδιάταξη Χωρών μεταξύ Λύσεων Leetcode Words

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

string reorderSpaces(string text) 
{
        int count=0;
        stringstream ss;
        vector<string> list;
        for(int i=0;i<text.length();i++){
            if(text[i]==' '){
                if(ss.str().size()>0)list.push_back(ss.str());//if there is some character present, only then 
                // insert into list
                count++;
                ss.str("");//empties the stringstream object
            }else{
                ss<<text[i];
            }
        }
        if(ss.str().size()>0)list.push_back(ss.str());//in case if any string is after the last space, that is not inserted into list.
        
        
        int wid=0,rem=0,l=0;
        if(list.size()==1){
            wid=0;
            rem=count;
        }else{
        /*number of positions between n words is n-1. thus l = list.size()-1*/
        l=list.size()-1;
        /*distributing the spaces equally in l places*/
        wid=count/l;
        /*and the remaining spaces will be appended at last*/
        rem=count%l;
        }
        ss.str("");
        for(int i=0;i<list.size();i++){
            ss<<list[i];//appending a word
            int w=wid;
            if(i<list.size()-1)
            while(w--!=0)ss<<' ';//appending spaces which is width we calculated above
        }
        while(rem--!=0)ss<<' ';//finally appending all the remaining spaces
        return ss.str();
}

int main()
{
    cout << reorderSpaces("  this   is  a sentence ");
}
this   is   a   sentence

Πρόγραμμα Java για αναδιάταξη χώρων μεταξύ λέξεων Leetcode Solution

import java.util.*;
import java.lang.*;

class Rextester
{  
    public static void main(String args[])
    {
        System.out.println(reorderSpaces("  this   is  a sentence "));
    }
    
    public static String reorderSpaces(String text) 
    {
        int count=0;
        StringBuilder sb=new StringBuilder();
        List<String> list=new ArrayList<String>();
        for(int i=0;i<text.length();i++){
            if(text.charAt(i)==' '){
                if(sb.length()>0)list.add(sb.toString());//if there is some non-space character also present, only then 
                // insert into list
                count++;//counting spaces
                sb=new StringBuilder();//empties the stringstream object
            }else{
                sb.append(text.charAt(i));
            }
        }
        if(sb.length()>0)list.add(sb.toString());//in case if any string is after the last space, that is not inserted into list.
        
        
        int wid=0,rem=0,l=0;
        if(list.size()==1){
            wid=0;
            rem=count;
        }else{
       /*number of positions between n words is n-1. thus l = list.size()-1*/
        l=list.size()-1;
      /*distributing the spaces equally in l places*/
        wid=count/l;
       /*and the remaining spaces will be appended at last*/
        rem=count%l;
        }
        sb=new StringBuilder();
        for(int i=0;i<list.size();i++){
            sb.append(list.get(i));//appending a word
            int w=wid;
            if(i<list.size()-1)
            while(w--!=0)sb.append(' ');//appending spaces which is width we calculated above
        }
        while(rem--!=0)sb.append(' ');//finally appending all the remaining spaces
        return sb.toString();
    }
}
this   is   a   sentence

Ανάλυση πολυπλοκότητας για αναδιάταξη διαστημάτων μεταξύ λέξεων Leetcode Solution

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

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

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

Επί): Έχουμε χρησιμοποιήσει γραμμικό επιπλέον χώρο με τη μορφή Λίστα λέξεων και συμβολοσειράς (ροή συμβολοσειράς σε περίπτωση cpp).