Last updated on July 16th, 2024 at 04:17 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

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 0 and not exceed maxWidth.
The input array words contains 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&lt;string&gt; fullJustify(vector&lt;string&gt;&amp; words, int maxWidth) {
        vector&lt;string&gt;res;
        if(maxWidth == 0) return {""};
        int i = 0, j = 0;
        while(j != words.size()){
            int len = -1;
            while(j &lt; words.size() &amp;&amp; len + words[j].size() + 1 &lt;= 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() &amp;&amp; (k == j - 1 || k == j)) k = i;
                if(j == words.size() &amp;&amp; k == j) k = j - 1;
            }
            string line = "";
            for(int l = i; l &lt; 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&lt;String&gt; fullJustify(String[] words, int maxWidth) {
        List&lt;String&gt; lines = new ArrayList&lt;String&gt;();
      
        int index = 0;
        while (index &lt; words.length) {
            int count = words[index].length();
            int last = index + 1;
            while (last &lt; words.length) {
                if (words[last].length() + count + 1 &gt; 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 &lt; last; i++) {
                    builder.append(words[i] + " ");
                }
                builder.deleteCharAt(builder.length() - 1);
                for (int i = builder.length(); i &lt; maxWidth; i++) {
                    builder.append(" ");
                }
            } else {
                int spaces = (maxWidth - count) / diff;
                int r = (maxWidth - count) % diff;
                for (int i = index; i &lt; last; i++) {
                    builder.append(words[i]);
                    if (i &lt; last - 1) {
                        for (int j = 0; j &lt;= (spaces + ((i - index) &lt; 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 =&gt; {
        if (word.length &lt;= (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) =&gt; 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-- &gt; 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 &lt; N:
            oneLine, j, currWidth, positionNum, spaceNum = [words[i]], i + 1, len(words[i]), 0,maxWidth - len(words[i])
            while j &lt; N and currWidth + 1 + len(words[j]) &lt;= maxWidth:
                oneLine.append(words[j])
                currWidth += 1 + len(words[j])
                spaceNum -= len(words[j])
                positionNum, j = positionNum + 1, j + 1
            i = j
            if i &lt; N and positionNum:
                spaces = [' ' * (spaceNum / positionNum + (k &lt; 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 result

4.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.