Last updated on October 10th, 2024 at 12:55 am
Here, We see Text Justification LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc., with different approaches.
List of all LeetCode Solution
Topics
String
Companies
Airbnb, Facebook, LinkedIn
Level of Question
Hard
Text Justification LeetCode Solution
Table of Contents
Problem Statement
Given an array of strings words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.
Note:
- A word is defined as a character sequence consisting of non-space characters only.
- Each word’s length is guaranteed to be greater than
0and not exceed maxWidth. - The input array
wordscontains at least one word.
Example 1: Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16 Output: [ "This is an", "example of text", "justification. " ]
Example 2: Input: words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16 Output: [ "What must be", "acknowledgment ", "shall be " ] Explanation: Note that the last line is "shall be " instead of "shall be", because the last line must be left-justified instead of fully-justified. Note that the second line is also left-justified because it contains only one word. Example 3: Input: words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"], maxWidth = 20 Output: [ "Science is what we", "understand well", "enough to explain to", "a computer. Art is", "everything else we", "do " ]
1. Text Justification Leetcode Solution C++
class Solution {
public:
vector<string> fullJustify(vector<string>& words, int maxWidth) {
vector<string>res;
if(maxWidth == 0) return {""};
int i = 0, j = 0;
while(j != words.size()){
int len = -1;
while(j < words.size() && len + words[j].size() + 1 <= maxWidth)
len += words[j++].size() + 1;
int space = maxWidth - len + j - i - 1;
int k = i;
while(space){
words[k++] += " ";
space--;
if(j != words.size() && (k == j - 1 || k == j)) k = i;
if(j == words.size() && k == j) k = j - 1;
}
string line = "";
for(int l = i; l < j; l++)
line += words[l];
res.push_back(line);
i = j;
}
return res;
}
};1.1 Explanation
- Initialization: res stores the result. i and j are indices to traverse the words.
- Outer while loop: Runs until j reaches the end of words.
- Inner while loop: Accumulates words in a line until the length exceeds maxWidth.
- Calculate spaces: space calculates extra spaces needed to justify the line.
- Distribute spaces: Distributes spaces among words evenly.
- Construct line: Constructs the justified line and adds it to res.
1.2 Time Complexity
O(n)
1.3 Space Complexity
- O(n * m), where n is the number of words and m is the average length of the words.
2. Text Justification Leetcode Solution Java
class Solution {
public List<String> fullJustify(String[] words, int maxWidth) {
List<String> lines = new ArrayList<String>();
int index = 0;
while (index < words.length) {
int count = words[index].length();
int last = index + 1;
while (last < words.length) {
if (words[last].length() + count + 1 > maxWidth) break;
count += words[last].length() + 1;
last++;
}
StringBuilder builder = new StringBuilder();
int diff = last - index - 1;
if (last == words.length || diff == 0) {
for (int i = index; i < last; i++) {
builder.append(words[i] + " ");
}
builder.deleteCharAt(builder.length() - 1);
for (int i = builder.length(); i < maxWidth; i++) {
builder.append(" ");
}
} else {
int spaces = (maxWidth - count) / diff;
int r = (maxWidth - count) % diff;
for (int i = index; i < last; i++) {
builder.append(words[i]);
if (i < last - 1) {
for (int j = 0; j <= (spaces + ((i - index) < r ? 1 : 0)); j++) {
builder.append(" ");
}
}
}
}
lines.add(builder.toString());
index = last;
}
return lines;
}
}2.1 Explanation
- Initialization: lines stores the result lines. index tracks the current word.
- Outer while loop: Iterates until index reaches the end of words.
- Inner while loop: Accumulates words in a line until the length exceeds maxWidth.
- Construct line: Uses StringBuilder to build the justified line.
- Distribute spaces: Calculates spaces and distributes them among words.
- Add to result: Adds the constructed line to lines.
2.2 Time Complexity
- O(n).
2.3 Space Complexity
- O(n * m), where n is the number of words and m is the average length of the words.
3. Text Justification Leetcode Solution JavaScript
var fullJustify = function(words, maxWidth) {
const res = [];
let buf = [];
let width = maxWidth;
words.forEach(word => {
if (word.length <= (width - buf.length)) {
buf.push(word);
width -= word.length;
} else {
addWordToResult(res, buf.slice(), maxWidth);
buf = [word];
width = maxWidth - word.length;
}
});
if (buf.length) {
let str = buf.join(' ');
str += ' '.repeat(maxWidth - str.length);
res.push(str);
}
return res;
};
function addWordToResult(res, buf, maxWidth) {
let spaces = maxWidth - buf.reduce((acc, cur) => cur.length + acc, 0);
if (buf.length === 1) {
buf[0] += ' '.repeat(spaces);
res.push(buf[0]);
return;
}
spaces -= buf.length - 1;
const end = buf.length - 1;
let index = 0;
while (spaces-- > 0) {
buf[index] += ' ';
index = (index + 1) % end;
}
res.push(buf.join(' '))
};3.1 Explanation
- Initialization: res stores the result lines. buf buffers words for the current line. width tracks remaining width.
- Processing words: Iterates through each word, accumulating them in buf.
- Add to result: Adds buf to res when the current word exceeds the line width.
- Distribute spaces: Evenly distributes spaces among words.
3.2 Time Complexity
- O(n).
3.3 Space Complexity
- O(n * m), where n is the number of words and m is the average length of the words.
4. Text Justification Leetcode Solution Python
class Solution(object):
def fullJustify(self, words, maxWidth):
i, N, result = 0, len(words), []
while i < N:
oneLine, j, currWidth, positionNum, spaceNum = [words[i]], i + 1, len(words[i]), 0,maxWidth - len(words[i])
while j < N and currWidth + 1 + len(words[j]) <= maxWidth:
oneLine.append(words[j])
currWidth += 1 + len(words[j])
spaceNum -= len(words[j])
positionNum, j = positionNum + 1, j + 1
i = j
if i < N and positionNum:
spaces = [' ' * (spaceNum / positionNum + (k < spaceNum % positionNum)) for k in range(positionNum)] + ['']
else:
spaces = [' '] * positionNum + [' ' * (maxWidth - currWidth)]
result.append(''.join([s for pair in zip(oneLine, spaces) for s in pair]))
return result4.1 Explanation
- Initialization: result stores the result lines. i and j are indices to traverse the words..
- Outer while loop: Runs until i reaches the end of words.
- Inner while loop: Accumulates words in a line until the length exceeds maxWidth.
- Calculate spaces: spaceNum calculates extra spaces needed to justify the line.
- Distribute spaces: Distributes spaces among words evenly.
- Construct line: Constructs the justified line and adds it to result.
4.2 Time Complexity
- O(N * W), where N is the number of words and W is the max width.
4.3 Space Complexity
- O(N * W), where N is the number of words and W is the max width.