Text Justification - LeetCode Solution in C++, Java, Python

1. Introduction

The "Text Justification" problem requires arranging a given array of words into fully justified text. The text should be formatted so that each line contains exactly maxWidth characters with appropriate spacing between words. The solution should use a greedy approach for word packing and handle special cases for spacing and the last line of text.

2. Problem

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. The last line should be left-justified with no extra space between words.

3. Solution in C++

vector<string> fullJustify(vector<string>& words, int maxWidth) {
    vector<string> result;
    int i = 0, n = words.size();
    while (i < n) {
        int j = i, len = 0;
        while (j < n && len + words[j].length() + j - i <= maxWidth)
            len += words[j++].length();

        string out;
        int extraSpaces = maxWidth - len;
        if (j == n || j - i == 1) {
            for (int k = i; k < j; ++k)
                out += words[k] + " ";
            out.resize(maxWidth, ' ');
        } else {
            int spaces = extraSpaces / (j - i - 1);
            int r = extraSpaces % (j - i - 1);
            for (int k = i; k < j; ++k) {
                out += words[k];
                if (k < j - 1)
                    out += string(spaces + (k - i < r), ' ');
            }
        }
        result.push_back(out);
        i = j;
    }
    return result;
}

Explanation:

1. Iterate through words, determining the number of words that fit in each line.

2. Calculate the number of spaces needed to justify the text.

3. Handle special cases for the last line and lines with a single word.

4. Distribute extra spaces evenly among words, giving preference to leftmost spaces when they don't divide evenly.

5. Add each justified line to the result.

4. Solution in Java

public List<String> fullJustify(String[] words, int maxWidth) {
    List<String> result = new ArrayList<>();
    int i = 0, n = words.length;
    while (i < n) {
        int j = i, len = 0;
        while (j < n && len + words[j].length() + j - i <= maxWidth)
            len += words[j++].length();

        StringBuilder out = new StringBuilder();
        int extraSpaces = maxWidth - len;
        if (j == n || j - i == 1) {
            for (int k = i; k < j; ++k)
                out.append(words[k]).append(" ");
            while (out.length() < maxWidth) out.append(" ");
        } else {
            int spaces = extraSpaces / (j - i - 1);
            int r = extraSpaces % (j - i - 1);
            for (int k = i; k < j; ++k) {
                out.append(words[k]);
                if (k < j - 1)
                    out.append(" ".repeat(Math.max(0, spaces + (k - i < r ? 1 : 0))));
            }
        }
        result.add(out.toString());
        i = j;
    }
    return result;
}

Explanation:

1. Loop through words, determining how many words fit on a line.

2. Use a StringBuilder to build each line.

3. Calculate extra spaces and distribute them evenly, with special handling for the last line and single-word lines.

4. Append each justified line to result.

5. Solution in Python

def fullJustify(words, maxWidth):
    result, 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)] += ' '
            result.append(''.join(cur))
            cur, num_of_letters = [], 0
        cur += [w]
        num_of_letters += len(w)

    return result + [' '.join(cur).ljust(maxWidth)]

Explanation:

1. Iterate over words, grouping words that fit within maxWidth into cur.

2. Distribute extra spaces when maxWidth is exceeded or the end is reached.

3. Special handling for the last line: left-justified with spaces at the end.

4. Add each line to result, joining words and padding right with spaces if necessary.