単語間のスペースを再配置するLeetcodeSolution


難易度 簡単に
よく聞かれる Google
文字列

問題文

この問題では、テキストが与えられます 文字列 スペースの間にいくつかの単語が配置されています。 単語には小文字の英字しか使用できません。 もちろん、各単語は少なくともXNUMXつのスペースで区切られます。 また、テキストには少なくともXNUMXつの単語があります。
例:text =”練習は完璧になります”
ご覧のとおり、任意の数のスペースがあります。
テキストを、各単語の間に同じ数のスペースが存在する形式に変換する必要があります。スペースが残っている場合、それらは最後の単語の後に累積されます。
スペースの総数を変更する必要はありません。 また、単語の順序は変更しないでください。

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

説明:

単語間のスペースを再配置するLeetcodeSolution

7つのスペースと3つの単語があります。
単語間の7-3 = 1のギャップに合うように、2つのスペースを均等に分割します。 したがって、出力では、単語間に7/2 = 3のスペースがあり、残りのスペースは最後の単語の後に累積されます。
したがって、出力は「練習は完璧になります」になります。

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

説明:

全部で9つのスペースと4つの単語があります。 単語間で9つのスペースを均等に分割できます:9 /(4-1)= 3つのスペース。

アプローチ

ここではXNUMXつのタスクを実行する必要があります。 最初は、与えられた入力からすべての単語を取得することです 文字列。 次に、スペースを数える必要があります。 この目的のために、入力文字列を線形にトラバースしています。 見つかった文字がスペースの場合、XNUMXつのことを行います。XNUMXつはこのスペースをカウントすること、もうXNUMXつは現在の単語を終了して単語リストに挿入することです。
現在の文字がスペースでない場合は、現在の単語に追加するだけです。 最後に、最後のスペースの後に単語が表示されている場合は、トラバーサルの後にその単語も追加します。

したがって、入力文字列内のスペースの数と単語を取得します。 次に、スペースを単語間で均等に分割する必要があります。 ただし、入力文字列に単語がXNUMXつしかないというエッジケースに注意する必要があるため、この単語の後にすべてのスペースが続く文字列を返す必要があります。 それ以外の場合は、これらのスペースを単語のリスト間で均等に分割する必要があります。

n個の単語がある場合、単語間の位置はn-1であるとします。
したがって、スペース(カウントしましょう)をこれらのn-1の場所に分割する必要があります
したがって、floor(count / n-1)は、すべての単語を区切るスペースの幅になります。
残りのスペースは最後の単語の後に追加されます。
つまり、count%(n-1)は残りのスペース数になります。

最後に、各単語と単語の各ペア間のフロア(count / n-1)スペース数、および最後の単語の後のスペース数%(n-1)を追加し続け、最後の文字列を返します。

製品の導入

C ++プログラムは単語間のスペースを再配置しますLeetcodeSolution

#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プログラムLeetcodeSolution

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

単語間のスペースを再配置するための複雑さの分析LeetcodeSolution

時間の複雑さ

オン): まず、入力文字列を線形にトラバースし、スペースで区切られた単語をリストに格納します。 次に、線形時間で出力文字列を作成しています。 したがって、時間計算量はO(n)になります。

スペースの複雑さ 

オン): 単語リストと文字列ビルダー(cppの場合は文字列ストリーム)の形式で線形の余分なスペースを使用しました。