ಪದಗಳ ನಡುವೆ ಸ್ಥಳಗಳನ್ನು ಮರುಹೊಂದಿಸಿ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಗೂಗಲ್
ಸ್ಟ್ರಿಂಗ್

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

ಈ ಸಮಸ್ಯೆಯಲ್ಲಿ, ನಮಗೆ ಪಠ್ಯವನ್ನು ನೀಡಲಾಗಿದೆ ಸ್ಟ್ರಿಂಗ್ ಸ್ಥಳಗಳ ನಡುವೆ ಇರಿಸಲಾಗಿರುವ ಕೆಲವು ಸಂಖ್ಯೆಯ ಪದಗಳನ್ನು ಹೊಂದಿದೆ. ಪದಗಳು ಸಣ್ಣ ಅಕ್ಷರಗಳನ್ನು ಮಾತ್ರ ಹೊಂದಬಹುದು. ಪ್ರತಿ ಪದಗಳನ್ನು ಕನಿಷ್ಠ ಒಂದು ಸ್ಥಳದೊಂದಿಗೆ ಬೇರ್ಪಡಿಸಲಾಗಿದೆ. ಪಠ್ಯವು ಕನಿಷ್ಠ ಒಂದು ಪದವನ್ನು ಹೊಂದಿದೆ.
ಉದಾ. ಪಠ್ಯ = ”ಅಭ್ಯಾಸವು ಪರಿಪೂರ್ಣವಾಗಿಸುತ್ತದೆ”
ನಾವು ನೋಡುವಂತೆ ಅನಿಯಂತ್ರಿತ ಸಂಖ್ಯೆಯ ಸ್ಥಳಗಳಿವೆ.
ನಾವು ಪಠ್ಯವನ್ನು ಅಂತಹ ಸ್ವರೂಪಕ್ಕೆ ಪರಿವರ್ತಿಸಬೇಕು, ಇದರಲ್ಲಿ ಪ್ರತಿ ಪದದ ನಡುವೆ ಸಮಾನ ಸಂಖ್ಯೆಯ ಸ್ಥಳಗಳಿವೆ ಮತ್ತು ಯಾವುದೇ ಸ್ಥಳವು ಉಳಿದಿದ್ದರೆ, ಕೊನೆಯ ಪದದ ನಂತರ ಅವು ಸಂಗ್ರಹಗೊಳ್ಳುತ್ತವೆ.
ನಾವು ಒಟ್ಟು ಸ್ಥಳಗಳ ಸಂಖ್ಯೆಯನ್ನು ಬದಲಾಯಿಸಬೇಕಾಗಿಲ್ಲ. ಅಲ್ಲದೆ ಪದಗಳ ಅನುಕ್ರಮವನ್ನು ಬದಲಾಯಿಸಬಾರದು.

ಉದಾಹರಣೆ

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

ವಿವರಣೆ:

ಪದಗಳ ನಡುವೆ ಸ್ಥಳಗಳನ್ನು ಮರುಹೊಂದಿಸಿ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ

ಇದು 7 ಸ್ಥಳಗಳು ಮತ್ತು 3 ಪದಗಳನ್ನು ಹೊಂದಿದೆ.
ಪದಗಳ ನಡುವಿನ 7-3 = 1 ಅಂತರಗಳಿಗೆ ಸರಿಹೊಂದುವಂತೆ ನಾವು 2 ಸ್ಥಳಗಳನ್ನು ಸಮಾನವಾಗಿ ವಿಭಜಿಸುತ್ತೇವೆ. ಹೀಗಾಗಿ, ನಮ್ಮ output ಟ್‌ಪುಟ್‌ನಲ್ಲಿ ನಾವು ಪದಗಳ ನಡುವೆ 7/2 = 3 ಸ್ಥಳಗಳನ್ನು ಹೊಂದಿರುತ್ತೇವೆ ಮತ್ತು ಕೊನೆಯ ಪದದ ನಂತರ 7-6 = 1 ಉಳಿದ ಜಾಗವನ್ನು ಸಂಗ್ರಹಿಸಲಾಗುತ್ತದೆ.
ಆದ್ದರಿಂದ output ಟ್‌ಪುಟ್ “ಅಭ್ಯಾಸವು ಪರಿಪೂರ್ಣವಾಗಿಸುತ್ತದೆ”.

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

ವಿವರಣೆ:

ಒಟ್ಟು 9 ಸ್ಥಳಗಳು ಮತ್ತು 4 ಪದಗಳಿವೆ. ನಾವು 9 ಸ್ಥಳಗಳನ್ನು ಪದಗಳ ನಡುವೆ ಸಮವಾಗಿ ವಿಂಗಡಿಸಬಹುದು: 9 / (4-1) = 3 ಸ್ಥಳಗಳು.

ಅಪ್ರೋಚ್

ನಾವು ಇಲ್ಲಿ ಎರಡು ಕಾರ್ಯಗಳನ್ನು ಮಾಡಬೇಕು. ಗಿವ್ ಇನ್ಪುಟ್ನಿಂದ ಎಲ್ಲಾ ಪದಗಳನ್ನು ಪಡೆಯುವುದು ಮೊದಲನೆಯದು ಸ್ಟ್ರಿಂಗ್. ಎರಡನೆಯದಾಗಿ, ನಾವು ಸ್ಥಳಗಳನ್ನು ಎಣಿಸಬೇಕು. ಈ ಉದ್ದೇಶಕ್ಕಾಗಿ, ನಾವು ಇನ್ಪುಟ್ ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ರೇಖೀಯವಾಗಿ ಹಾದುಹೋಗುತ್ತಿದ್ದೇವೆ. ಕಂಡುಬರುವ ಅಕ್ಷರವು ಒಂದು ಸ್ಥಳವಾಗಿದ್ದರೆ ನಾವು ಎರಡು ಕೆಲಸಗಳನ್ನು ಮಾಡುತ್ತೇವೆ, ಒಂದು ಈ ಜಾಗವನ್ನು ಎಣಿಸುವುದು ಮತ್ತು ಇನ್ನೊಂದು ಪ್ರಸ್ತುತ ಪದವನ್ನು ಕೊನೆಗೊಳಿಸುವುದು ಮತ್ತು ಅದನ್ನು ಪದಗಳ ಪಟ್ಟಿಗೆ ಸೇರಿಸುವುದು.
ಪ್ರಸ್ತುತ ಅಕ್ಷರವು ಸ್ಥಳಾವಕಾಶವಿಲ್ಲದಿದ್ದರೆ ನಾವು ಅದನ್ನು ನಮ್ಮ ಪ್ರಸ್ತುತ ಪದಕ್ಕೆ ಸೇರಿಸುತ್ತೇವೆ. ಕೊನೆಗೆ, ಕೊನೆಯ ಜಾಗದ ನಂತರ ಯಾವುದೇ ಪದವು ಗೋಚರಿಸುತ್ತಿದ್ದರೆ, ನಾವು ಆ ಪದವನ್ನು ಅಡ್ಡಾದಿಡ್ಡಿಯ ನಂತರವೂ ಸೇರಿಸುತ್ತೇವೆ.

ಆದ್ದರಿಂದ, ನಾವು ಇನ್ಪುಟ್ ಸ್ಟ್ರಿಂಗ್ನಲ್ಲಿ ಸ್ಥಳಗಳ ಸಂಖ್ಯೆ ಮತ್ತು ಪದಗಳನ್ನು ಪಡೆಯುತ್ತೇವೆ. ಈಗ ನಾವು ಸ್ಥಳಗಳನ್ನು ಪದಗಳ ನಡುವೆ ಸಮಾನವಾಗಿ ವಿಂಗಡಿಸಬೇಕು. ಆದರೆ ಇನ್ಪುಟ್ ಸ್ಟ್ರಿಂಗ್ನಲ್ಲಿ ಕೇವಲ ಒಂದೇ ಪದವಿರಬಹುದೆಂದು ನಾವು ಎಡ್ಜ್ ಕೇಸ್ ಅನ್ನು ಗಮನಿಸಬೇಕು, ಆದ್ದರಿಂದ ನಾವು ಈ ಪದವನ್ನು ಹೊಂದಿರುವ ಎಲ್ಲಾ ಸ್ಟ್ರಿಂಗ್ಗಳನ್ನು ಹೊಂದಿರುವ ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ಹಿಂತಿರುಗಿಸಬೇಕಾಗಿದೆ. ಇಲ್ಲದಿದ್ದರೆ, ನಾವು ಈ ಸ್ಥಳಗಳನ್ನು ಪದಗಳ ಪಟ್ಟಿಯಲ್ಲಿ ಸಮಾನವಾಗಿ ವಿಂಗಡಿಸಬೇಕು.

N ಪದಗಳಿದ್ದರೆ, ಪದಗಳ ನಡುವಿನ ಸ್ಥಾನಗಳು n-1 ಎಂದು ಭಾವಿಸೋಣ.
ಹೀಗಾಗಿ, ನಾವು ಸ್ಥಳಗಳನ್ನು (ಎಣಿಸೋಣ) ಈ n-1 ಸ್ಥಳಗಳಾಗಿ ವಿಂಗಡಿಸಬೇಕು
ಆದ್ದರಿಂದ ನೆಲ (ಎಣಿಕೆ / ಎನ್ -1) ಎಲ್ಲಾ ಪದಗಳನ್ನು ಬೇರ್ಪಡಿಸುವ ಸ್ಥಳಗಳ ಅಗಲವಾಗಿರುತ್ತದೆ.
ಮತ್ತು ಉಳಿದ ಸಂಖ್ಯೆಯ ಸ್ಥಳಗಳನ್ನು ಕೊನೆಯ ಪದದ ನಂತರ ಸೇರಿಸಲಾಗುತ್ತದೆ.
ಅಂದರೆ ಎಣಿಕೆ% (n-1) ಉಳಿದ ಸಂಖ್ಯೆಯ ಸ್ಥಳಗಳಾಗಿರುತ್ತದೆ.

ಅಂತಿಮವಾಗಿ, ನಾವು ಪ್ರತಿ ಪದ ಮತ್ತು ಪ್ರತಿ ಜೋಡಿ ಪದಗಳ ನಡುವಿನ ನೆಲದ (ಎಣಿಕೆ / ಎನ್ -1) ಸಂಖ್ಯೆಯ ಸ್ಥಳಗಳನ್ನು ಸೇರಿಸುತ್ತಲೇ ಇರುತ್ತೇವೆ ಮತ್ತು ಕೊನೆಯ ಪದದ ನಂತರ% (n-1) ಸಂಖ್ಯೆಯ ಸ್ಥಳಗಳನ್ನು ಎಣಿಸುತ್ತೇವೆ ಮತ್ತು ಅಂತಿಮ ದಾರವನ್ನು ಹಿಂತಿರುಗಿಸುತ್ತೇವೆ.

ಅನುಷ್ಠಾನ

ಸಿ ++ ಪ್ರೋಗ್ರಾಂ ಪದಗಳ ನಡುವೆ ಸ್ಥಳಗಳನ್ನು ಮರುಹೊಂದಿಸಿ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ

#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

ಪದಗಳ ನಡುವಿನ ಮರುಹೊಂದಿಸುವ ಸ್ಥಳಗಳಿಗೆ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್): ಮೊದಲನೆಯದಾಗಿ, ನಾವು ನಮ್ಮ ಇನ್ಪುಟ್ ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ರೇಖೀಯವಾಗಿ ಹಾದುಹೋಗುತ್ತಿದ್ದೇವೆ ಮತ್ತು ಸ್ಥಳದಿಂದ ಬೇರ್ಪಟ್ಟ ಪದಗಳನ್ನು ನಮ್ಮ ಪಟ್ಟಿಯಲ್ಲಿ ಸಂಗ್ರಹಿಸುತ್ತಿದ್ದೇವೆ. ನಂತರ, ನಾವು ನಮ್ಮ output ಟ್‌ಪುಟ್ ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ರೇಖೀಯ ಸಮಯದಲ್ಲಿ ರಚಿಸುತ್ತಿದ್ದೇವೆ. ಹೀಗಾಗಿ, ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು O (n) ಆಗಿರುತ್ತದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ 

ಒ (ಎನ್): ಪದಗಳ ಪಟ್ಟಿ ಮತ್ತು ಸ್ಟ್ರಿಂಗ್ ಬಿಲ್ಡರ್ (ಸಿಪಿಪಿಯ ಸಂದರ್ಭದಲ್ಲಿ ಸ್ಟ್ರಿಂಗ್ ಸ್ಟ್ರೀಮ್) ರೂಪದಲ್ಲಿ ನಾವು ರೇಖೀಯ ಹೆಚ್ಚುವರಿ ಜಾಗವನ್ನು ಬಳಸಿದ್ದೇವೆ.