لفظن Leetcode حل جي وچ ۾ ٻيهر ترتيب ڏيڻ جي جاءِ


تڪليف جي سطح آسان
بار بار پڇڻ ۾ گوگل
اسٽرنگ

مسئلي جو بيان

ھن مسئلي ۾ ، اسان کي ھڪڙو متن ڏنو وڃي ٿو جملو ڪي لفظ هجڻ سان گڏ جڳهن ۾ رکيل آهن. لفظن ۾ صرف انگريزي وارا نن lowerا اکر هوندا. يقينن هر لفظ گهٽ ۾ گهٽ هڪ جڳهه سان جدا ٿيل آهي. پڻ متن ۾ گھٽ ۾ گھٽ ھڪڙو لفظ آھي.
مثال طور متن = ”مشق مڪمل ڪندو آهي“
جئين اسان ڏسي سگھون ٿا اتي وڏو تعداد جي جاءِ آهي.
اسان کي هڪ متن کي اهڙي شڪل ۾ بدلڻو آهي جنهن ۾ هر لفظ جي وچ ۾ جيترا خلا موجود هجن ۽ جيڪڏهن ڪا جڳهه رهي ته پوءِ اهي آخري لفظ کان پوءِ گڏ ڪيا ويندا.
اسان کي خلائي تعداد جو مٽائڻو ناهي. پڻ لفظن جي تسلسل کي تبديل نه ڪرڻ گهرجي.

مثال

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 جڳهن.

چرچو

اسان کي هتي ٻه ڪم ڪرڻا آهن. پهرين ته آهي ان لفظ کي ڏيو ان پٽ مان جملو. ٻيون ، اسان کي جڳهيون ڳڻپ ڪرڻ گهرجن. هن مقصد لاءِ ، اسان لڪير کي لڪائيندي انٽري اسٽرنگ کي پار ڪري رهيا آهيون. جيڪڏهن جيڪو ڪردار مليو هڪ خلائي آهي پوءِ اسين ٻه شيون ڪريون ٿا هڪ اهو ته آهي هن جڳهه کي ڳڻڻ ۽ ٻيو اهو موجوده لفظ کي ختم ڪرڻ ۽ لفظ جي فهرست ۾ داخل ڪرڻ.
جيڪڏھن موجوده ڪردار خلا نه آھي ته پوءِ ھ hanya اسان ان کي پنھنجي موجوده لفظ ۾ شامل ڪيو. آخر ۾ ، جيڪڏهن ڪو لفظ آخري جاءِ کان پوءِ ظاهر ٿي رهيو آهي ، اسان لفظ به جدي کانپوءِ شامل ڪيو ٿا.

تنهن ڪري ، اسان کي جڳهن جو تعداد ۽ لفظن ۾ ان پٽڻ واري تار ۾ ملي ٿي. ھاڻي اسان کي جڳن کي برابر لفظن جي وچ ۾ ورهڻو پوندو. پر اسان کي هڪ ڪنڊ واري صورت ڏانهن ڏسڻو پوندو ته انپٽ واري اسٽرنگ ۾ صرف هڪ لفظ ٿي سگهي ٿو ، تنهن ڪري اسان کي رڳو هڪ اهڙي اسٽرنگ واپس ڪرڻي آهي جنهن ۾ اهو لفظ آهي سڀني جڳهن جي پٺيان. ٻي صورت ۾ ، اسان کي انهن جڳهن کي برابر لفظن جي فهرست ۾ ورهڻو آهي.

فرض ڪريو جيڪڏهن هتي نوان لفظ آهن ، ته پوءِ لفظن جي وچ وارو مقام N-1 آهن.
ان ڪري ، اسان کي جڳن کي (اڌ ڳڻيندڙ) کي n-1 جڳهن ۾ ورهڻو آهي
تنهن ڪري فرش (ڳڻپڻ / ن -1) جڳهن جي چوٿين هوندي جيڪا سڀني لفظن کي جدا ڪري ٿي.
۽ اسپاءِ جي باقي تعداد آخري لفظ کان پوءِ شامل ڪئي ويندي.
يعني ڳڻ٪٪ (n-1) باقي رهيل نمبرَ.

آخر ۾ ، اسان هر لفظ ۽ منزل جي فرش (شمار ​​/ ن -1) لفظ جي هر جوڙي جي وچ واري جڳهه جو نمبر تي رکندا سين ۽ آخري لفظ کان پوءِ اسپيس جي نمبر (n-1) نمبر ۽ آخري تار واپس آڻينداسين.

تي عملدرآمد

C ++ پروگرام لفظ جي وچ ۾ ٻيهر جڳھون ليٽ ڪوڊ حل

#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

جاوا پروگرام لفظ ليوٽ ڪوڊ حل جي وچ ۾ ٻيهر جڳهه لاءِ

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

الفاظ ليٽ ڪوڊ حل جي وچ ۾ حد جي ٻيهر جڳهه لاءِ پيچيدگي جو تجزيو

وقت جي پيچيدگي

اي (ن): پهرين ، اسان پنهنجي داخل ٿيندڙ اسٽرنگ کي لڪير سان لڪائي رهيا آهيون ۽ خلائي جدا جدا لفظن کي پنهنجي فهرست ۾ محفوظ ڪري رهيا آهيون. ان کان پوء ، اسان پنهنجي پيداوار واري اسٽرنگ کي لڪير وقت ۾ ٺاهي رهيا آهيون. ان ڪري ، وقت جي پيچيدگي O (n) ٿيندي.

خلائي پيچيدگي 

اي (ن): اسان لسٽ جي اضافي جڳھ جي طور تي لفظن جي فهرست ۽ اسٽرنگ بلڊر استعمال ڪيو آهي (سي پي پي جي صورت ۾ اسٽرنگ جو وهڪرو).