Text Justification LeetCode Solution

Here, We see Text Justification problem Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc., with different approaches.

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                  "
]

• C++ Solution
• Java Solution
• JavaScript Solution
• Python Solution

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;
    }
};
Code language: C++ (cpp)

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;
    }
}
Code language: Java (java)

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(' '))
};
Code language: JavaScript (javascript)

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 result
Code language: Python (python)