Solution For Text Justification

The Text Justification problem on LeetCode asks you to take in a list of words and an integer value representing the maximum number of characters that can fit on one line. You have to divide the words into lines such that each line has at most the maximum width and is fully justified. The final output should be a list of strings, where each string represents a line in the text. The text should be fully justified, which means that the spaces between the words in each line should be evenly distributed.

To solve this problem, you can follow these steps:

Step 1: Divide the words into lines
First, you need to divide the words into lines such that each line has at most the maximum width. You can do this by keeping track of the current line’s word count and the current line’s character count. Then, keep adding new words to the current line until the character count exceeds the maximum width. Once the maximum width is reached, start a new line and continue adding words to the new line until you run out of words.

Step 2: Fully justify each line
Once you have divided the words into lines, the next step is to fully justify each line. To do this, you need to add extra spaces between the words in each line. The number of extra spaces you need to add between the words will depend on the following factors:

• The total number of spaces left to fill in the line after adding the words
• The number of gaps between the words in the line

To distribute the spaces evenly, you can calculate the total number of spaces needed to fill in the line by subtracting the current line’s character count from the maximum width. Next, you need to calculate the total number of gaps between the words by counting the number of words in the line and subtracting one. Finally, you can distribute the spaces evenly among the gaps by dividing the total number of spaces by the number of gaps.

Step 3: Handle special cases
There are a few special cases you need to handle. For example, if a line has only one word, you don’t need to add any extra spaces between the words. Also, for the last line, you need to left-justify the text and not add any extra spaces at the end of the line.

Once you have followed these steps, you should have a fully justified text that meets the requirements of the Text Justification problem on LeetCode.

Step by Step Implementation For Text Justification

/**
 * Given an array of words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly maxWidth characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left justified and no extra space is inserted between words.

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 becase 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                  "
]
 */

import java.util.*;

public class TextJustification {
    public List fullJustify(String[] words, int maxWidth) {
        List result = new ArrayList<>();
        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 line or number of words in the line is 1, left-justified
            if (last == words.length || diff == 0) {
                for (int i = index; i < last; i++) {
                    builder.append(words[i] + " ");
                }
                builder.deleteCharAt(builder.length() - 1);
                while (builder.length() < maxWidth) {
                    builder.append(" ");
                }
            } else {
                // middle justified
                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(" ");
                        }
                    }
                }
            }
            result.add(builder.toString());
            index = last;
        }

        return result;
    }
}

def fullJustify(self, words, maxWidth):
        res, cur, num_of_letters = [], [], 0
        for w in words:
            if num_of_letters + len(w) + len(cur) > maxWidth:
                for i in range(maxWidth - num_of_letters):
                    cur[i%(len(cur)-1 or 1)] += ' '
                res.append(''.join(cur))
                cur, num_of_letters = [], 0
            cur += [w]
            num_of_letters += len(w)
        return res + [' '.join(cur).ljust(maxWidth)]

/**
 * @param {string[]} words
 * @param {number} maxWidth
 * @return {string[]}
 */
var fullJustify = function(words, maxWidth) {
    
    var result = [];
    
    for (var i = 0, len = words.length; i < len; i++) {
        var count = words[i].length;
        var last = i + 1;
        
        while (last < len && count + 1 + words[last].length <= maxWidth) {
            count += 1 + words[last].length;
            last++;
        }
        
        var line = words[i];
        
        var diff = last - i - 1;
        
        // if last line or number of words in the line is 1, left-justified
        if (last === len || diff === 0) {
            for (var j = i + 1; j < last; j++) {
                line += ' ' + words[j];
            }
            
            while (line.length < maxWidth) {
                line += ' ';
            }
        } else {
            // middle justified
            var space = (maxWidth - count) / diff;
            var r = (maxWidth - count) % diff;
            
            for (var j = i + 1; j < last; j++) {
                line += ' ';
                
                for (var k = 0; k < space; k++) {
                    line += ' ';
                }
                
                if (r > 0) {
                    line += ' ';
                    r--;
                }
                
                line += words[j];
            }
        }
        
        result.push(line);
        i = last - 1;
    }
    
    return result;
};

vector fullJustify(vector& words, int maxWidth) {
        vector res;
        for(int i = 0, k, l; i < words.size(); i += k) {
            for(k = l = 0; i + k < words.size() && l + words[i+k].size() <= maxWidth - k; k++) {
                l += words[i+k].size();
            }
            string tmp = words[i];
            for(int j = 0; j < k - 1; j++) {
                if(i + k >= words.size()) tmp += " ";
                else tmp += string((maxWidth - l) / (k - 1) + (j < (maxWidth - l) % (k - 1)), ' ');
                tmp += words[i+j+1];
            }
            tmp += string(maxWidth - tmp.size(), ' ');
            res.push_back(tmp);
        }
        return res;
    }

using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication1 { class Program { static void Main(string[] args) { string[] words = new string[] { "This", "is", "an", "example", "of", "text", "justification." }; int maxWidth = 16; List result = FullJustify(words, maxWidth); foreach (string s in result) { Console.WriteLine(s); } Console.ReadLine(); } public static List FullJustify(string[] words, int maxWidth) { List result = new List(); if (words == null || words.Length == 0) { return result; } int count = 0; int last = 0; for (int i = 0; i < words.Length; i++) { count = count + words[i].Length; if (count + i - last > maxWidth) { int wordsLen = count - words[i].Length; int spaceLen = maxWidth - wordsLen; int eachLen = 1; int extraLen = 0; if (i - last - 1 > 0) { eachLen = spaceLen / (i - last - 1); extraLen = spaceLen % (i - last - 1); } stringBuilder sb = new StringBuilder(); for (int j = last; j < i - 1; j++) { sb.Append(words[j]); int ce = 0; while (ce < eachLen) { sb.Append(" "); ce++; } if (extraLen > 0) { sb.Append(" "); extraLen--; } } sb.Append(words[i - 1]);//last words, not need space int dif = maxWidth - sb.Length; while (dif > 0) { sb.Append(" "); dif--; } result.Add(sb.ToString()); last = i; count = words[i].Length; } else { count = count + words[i].Length; } } int lastLen = 0; for (int i = last; i < words.Length; i++) { lastLen += words[i].Length; } stringBuilder sbLast = new StringBuilder(); for (int i = last; i < words.Length - 1; i++) { sbLast.Append(words[i] + " "); } sbLast.Append(words[words.Length - 1]); int dif2 = maxWidth - sbLast.Length - lastLen; while (dif2 > 0) { sbLast.Append(" "); dif2--; } result.Add(sbLast.ToString()); return result; } } }