Text Justification Problem Solution

Text Justification 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.

Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
Output:
[
   "This    is    an",
   "example  of text",
   "justification.  "
]

Text Justification Problem Solution

Problem Solution In Python

class Solution(object):
    def fullJustify(self, words, maxWidth):
        """
        :type words: List[str]
        :type maxWidth: int
        :rtype: List[str]
        """
        curr_line = []
        curr_line_width = 0
        lines = []
        
        for word in words:
            if len(word) + curr_line_width + len(curr_line) > maxWidth:
                # Need to add justified line
                nspaces = len(curr_line) - 1 if len(curr_line) - 1 else 1
                for i in range(maxWidth - curr_line_width):
                    curr_line[i % nspaces] += " "
                lines.append("".join(curr_line))
                curr_line = []
                curr_line_width = 0
            curr_line.append(word)
            curr_line_width += len(word)
        
        last_line = " ".join(curr_line)
        last_line = last_line.strip()
        last_line = last_line + " "*(maxWidth - len(last_line))
        lines.append(last_line)
        return lines

Problem Solution In Java

class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> res = new ArrayList<>();
        StringBuffer sb = new StringBuffer();
        int index = 0;
        while (index < words.length) {
            int count = 0;
            int total = 0;
            if (words[index].length() == maxWidth) {
                res.add(words[index]);
                index++;
                continue;
            }
            while (index < words.length && sb.length() + 1 + words[index].length() <= maxWidth) {
                count++;
                if (sb.length() > 0) {
                    sb.append(" ");
                }
                sb.append(words[index]);
                index++;
            }
            if (count == 1 || index == words.length) {
                while (sb.length() != maxWidth) {
                    sb.append(" ");
                }
                res.add(sb.toString());
                sb = new StringBuffer();
                continue;
            }
            String s = adjust(sb.toString(), maxWidth);
            res.add(s);
            sb = new StringBuffer();
        }
        return res;
    }
    private String adjust(String s, int max) {
        String[] array = s.split(" ");
        int total = 0;
        for (String s1 : array) {
            total += s1.length();
        }
        int remain = max - total;
        while (remain > 0) {
            for (int i = 0; i < array.length - 1; i++) {
                if (remain > 0) {
                    array[i] = array[i] + " ";
                    remain--;
                } else {
                    break;
                }
            }
        }
        StringBuffer sb = new StringBuffer();
        for (String s1 : array) {
            sb.append(s1);
        }
        return sb.toString();
    }
}

Problem Solution In C++

class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        int n = (int)words.size();
        int out = 0;
        vector<string> result;
        while (out < n) {
            int i = out;
            int curWidth = (int)words[i++].size();
            while (i < n && curWidth + 1 + (int)words[i].size() <= maxWidth) 
                curWidth += 1 + (int)words[i++].size();
            int numExtraSpace = maxWidth - curWidth;
            stringstream ss;
            int j = out;
            ss << words[j++];
            for (; j < i; j++) {
                int pad = 0;
                if (i < n) 
                    pad = numExtraSpace / (i-j) + (numExtraSpace % (i-j) ? 1 : 0);
                for (int k = 0; k < pad+1; k++)
                    ss << " ";
                numExtraSpace -= pad;
                ss << words[j];
            }
            for (int k = 0; k < numExtraSpace; k++)
                ss << " ";
            result.push_back(ss.str());
            out = i;
        }
        return result;
    }
};


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment