단어 사이의 공백 다시 정렬 Leetcode 솔루션


난이도 쉽게
자주 묻는 질문 구글

문제 정책

이 문제에서 우리는 공백 사이에 몇 개의 단어가 있습니다. 단어에는 소문자 영문 만 사용할 수 있습니다. 물론 각 단어는 적어도 하나의 공백으로 구분됩니다. 또한 텍스트에는 적어도 하나의 단어가 있습니다.
예 : text =”연습은 완벽을 만듭니다.”
보시다시피 임의의 수의 공간이 있습니다.
텍스트를 각 단어 사이에 동일한 수의 공백이있는 형식으로 변환해야하며 공백이 남아 있으면 마지막 단어 뒤에 누적됩니다.
총 공간 수를 변경할 필요가 없습니다. 또한 단어의 순서를 변경해서는 안됩니다.

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

설명 :

단어 사이의 공백 다시 정렬 Leetcode 솔루션

7 개의 공백과 3 개의 단어가 있습니다.
단어 사이의 7-3 = 1 간격에 맞게 2 개의 공백을 균등하게 나눌 것입니다. 따라서 출력에서 ​​단어 사이에 7 / 2 = 3 공백이 있고 마지막 단어 뒤에 7-6 = 1 남은 공백이 누적됩니다.
따라서 출력은“practice makes perfect”이됩니다.

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)와 마지막 단어 뒤에 공백 수를 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 Solution

시간 복잡성

의 위에): 첫째, 입력 문자열을 선형으로 탐색하고 공백으로 구분 된 단어를 목록에 저장합니다. 그런 다음 선형 시간으로 출력 문자열을 생성합니다. 따라서 시간 복잡도는 O (n)입니다.

공간 복잡성 

의 위에): 단어 목록 및 문자열 작성기 (cpp의 경우 문자열 스트림)의 형태로 선형 추가 공간을 사용했습니다.