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;
    }
};

Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment