We will discuss Text Justification LeetCode Solution today
Table of Contents
Problem Statement
The problem “Text Justification” states that you are given a list s[ ] of type string of size n and an integer size. Justify the text such that each line of text consists of size number of characters. You can use space(‘ ‘) as a character to complete the required number of characters in a line.
Example
s = {"TutorialCup", "is", "the", "best", "portal", "for", "programming."}
size = 12TutorialCup is the best portal for programming.
Explanation: As we can use spaces between the words, we have placed them properly as can be seen in the image embedded above.
s = {"This", "article", "is", "contributed", "by", "Akshita", "Jain"}
size = 13This article is contributed by Akshita Jain
Algorithm for Text Justification LeetCode Solution
- Initialize a list s[ ] of type string of size n and an integer variable size.
- Traverse through the list and check for each word/string if the length of the current word is less than or equal to the given size, add the current word to the result.
- Else if the length of the current string/word is greater than the given size, use the white spaces to complete the remaining positions of the line.
- If the sum of the length of the next word in the same line and the length of the previous word in the same line is less than or equal to the given size, add the current word to the result and adjust the remaining places with the white space.
- Else if the sum of the length of the next word in the same line and the length of the previous word in the same line is greater than the given size, add the current word in the next line of the result and fill the remaining places of current line with the white space.
- Print the resulting string.
Code
C++ Program of Text Justification
#include "bits/stdc++.h"
using namespace std;
string getSpaces(int n){
string s = "";
for(int i=0; i<n;i++) s += " ";
return s;
}
string getLine(vector<string>& words, int start, int end, int letterCount, int maxWidth){
string res = words[start];
int spaces = maxWidth - letterCount;
if(start == end){
res += getSpaces(spaces);
return res;
}
int numOfSpace = spaces/(end-start);
int extraOne = spaces%(end-start);
string space0 = getSpaces(numOfSpace);
string space1 = space0 + " ";
for(int i= 0; i< end-start; i++){
res = res + (i < extraOne? space1: space0) + words[start + 1 + i];
}
return res;
}
vector<string> fullJustify(vector<string>& words, int maxWidth) {
int N = words.size();
int i = 0, j = 0;
int counter = 0;
vector<string> res;
while(i<N && j<N){
int len = words[j].length();
counter += len;
if(counter + j - i > maxWidth){
counter -= len;
res.push_back(getLine(words, i, j-1, counter, maxWidth));
i = j;
counter = 0;
}
else{
j++;
}
}
if(counter){
string last = words[i];
for(int x=i+1; x < j; x++){
last = last + " " + words[x];
}
last = last + getSpaces(maxWidth - last.size());
res.push_back(last);
}
return res;
}
int main(){
vector<string> s = {"TutorialCup", "is", "the", "best", "portal", "for", "programming."};
int size = 12;
vector<string> lines = fullJustify(s, size);
for(auto x: lines)
cout << x << endl;
return 0;
}
TutorialCup is the best portal for programming.
Java Program of Text Justification
import java.util.*;
class TextJustification{
static List<String> fullJustify(String[] words, int maxWidth) {
List<String> res = new ArrayList<>();
int size = words.length;
int index = 0;
while (index < size){
int totalChars = words[index].length();
int lastIndex = index + 1;
int gaps = 0;
while (lastIndex < size){
if (totalChars + 1 + words[lastIndex].length() > maxWidth){
break;
}
totalChars += 1 + words[lastIndex++].length();
gaps++;
}
StringBuilder sb = new StringBuilder();
if (lastIndex == size || gaps == 0){
for (int i = index; i < lastIndex; ++i){
sb.append(words[i]).append(' ');
}
sb.deleteCharAt(sb.length() - 1);
while (sb.length() < maxWidth){
sb.append(' ');
}
}
else {
int spaces = (maxWidth - totalChars) / gaps;
int restSpaces = (maxWidth - totalChars) % gaps;
for (int i = index; i < lastIndex - 1; ++i){
sb.append(words[i]).append(' ');
for (int j = 0; j < spaces + (i - index < restSpaces ? 1 : 0); ++j){
sb.append(' ');
}
}
sb.append(words[lastIndex - 1]);
}
res.add(sb.toString());
index = lastIndex;
}
return res;
}
public static void main (String[] args){
String[] words = {"TutorialCup", "is", "the", "best", "portal", "for", "programming."};
int size = 12;
List<String> res = new ArrayList<String>();
res = fullJustify(words, size);
ListIterator<String> lItr = res.listIterator();
while (lItr.hasNext()){
System.out.println(lItr.next());
}
}
}
TutorialCup is the best portal for programming.
Complexity Analysis
Time Complexity
O(n) where n is size of the given string array s[ ]. We are running a while loop inside fullJustify which runs only until either of the i and j variable do not cross N. And this loop takes linear time to end. Thus time complexity is linear.
Space Complexity
O(n) because we used space to store n string.