Переставьте пробелы между словами Решение Leetcode


Сложный уровень Легко
Часто спрашивают в Google
строка

Постановка задачи

В этой задаче нам дан текст строка имея некоторое количество слов, помещенных между пробелами. В словах могут быть только строчные английские буквы. Конечно, каждое слово разделяется как минимум одним пробелом. Также в тексте есть хотя бы одно слово.
например, text = "практика делает совершенство"
Как видим, количество пробелов произвольное.
Мы должны преобразовать текст в такой формат, в котором между каждым словом есть равное количество пробелов, и если они останутся, то они будут накапливаться после последнего слова.
Нам не нужно менять общее количество пробелов. Также нельзя менять последовательность слов.

Пример

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 места
следовательно, floor (count / n-1) будет шириной пробелов, разделяющих все слова.
а оставшееся количество пробелов будет добавлено после последнего слова.
т.е. count% (n-1) будет оставшимся количеством пробелов.

Наконец, мы продолжим добавлять каждое слово и количество пробелов (count / n-1) между каждой парой слов и подсчитывать% (n-1) количество пробелов после последнего слова и возвращать последнюю строку.

Реализация

Программа на C ++ переставляет пробелы между словами Решение Leetcode

#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

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

Сложность времени

На): Во-первых, мы перемещаемся по строке ввода линейно и сохраняем слова, разделенные пробелами, в нашем списке. Затем мы создаем нашу выходную строку за линейное время. Таким образом, временная сложность будет O (n).

Космическая сложность 

На): Мы использовали линейное дополнительное пространство в виде списка слов и конструктора строк (поток строк в случае cpp).