重新排列单词之间的空格Leetcode解决方案


难度级别 易得奖学金
经常问 谷歌

问题陈述

在这个问题上,我们得到一个文本 绳子 在空格之间放置了一些单词。 单词只能有小写英文字母。 当然,每个单词至少要用一个空格隔开。 另外,该文本至少包含一个单词。
例如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)将是剩余的空格数。

最后,我们将继续在每个单词对和每个单词对之间的floor(count / n-1)个空格和最后一个单词之后的count%(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情况下为字符串流)形式的线性多余空间。