Question

Formatted question description: https://leetcode.ca/all/68.html

68	Text Justification

Given an array of words and a length L, format the text such that each line has exactly L 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 L 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.

For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.

Return the formatted lines as:
[
   "This    is    an",
   "example  of text",
   "justification.  "
]
Note: Each word is guaranteed not to exceed L in length.

Corner Cases:
A line other than the last line might contain only one word. What should you do in this case?
In this case, that line should be left-justified.

Algorithm

To justify text using the greedy approach, maintain a line of words and attempt to add new words followed by a space. If adding a new word (without adding another space) causes the total width to exceed maxWidth, then the current line cannot accommodate the new word. At this point, do text justification for the current line, add the justified current line to the result list, and start a new line with the new word.

For justification, start by removing the last space in the line. Next, calculate the number of spaces to be added between each pair of words. Calculate the remaining spaces and remaining splits, where the remaining splits equal the number of words in the line minus one. For each split from right to left, the number of spaces to be added equals the remaining spaces divided by the remaining splits (using integer division). Add the spaces and update the remaining spaces and remaining splits. Repeat this process until the remaining spaces become zero.

For the last line, remove the last space in the line, and append spaces at the end until the line’s width equals maxWidth.

Finally, return the result list.

Code

Java

public class Text_Justification {

    public static void main(String[] args) {

        Text_Justification out = new Text_Justification();
        Solution one = out.new Solution();


        System.out.println(one.fullJustify(new String[]{"This", "is", "an", "example", "of", "text", "justification."}, 16));
        System.out.println(one.fullJustify(new String[]{"a", "b", "c", "d", "e"}, 1));
        System.out.println(one.fullJustify(new String[]{"a", "b", "c", "d", "e"}, 3));

    }

    public class Solution {
        public List<String> fullJustify(String[] words, int maxWidth) {
            int left = 0; List<String> result = new ArrayList<>();

            while (left < words.length) {
                int right = findRight(left, words, maxWidth);
                result.add(justify(left, right, words, maxWidth));
                left = right + 1;
            }

            return result;
        }

        private int findRight(int left, String[] words, int maxWidth) {
            int right = left;
            int sum = words[right++].length();

            while (right < words.length && (sum + 1 + words[right].length()) <= maxWidth)
                sum += 1 + words[right++].length();

            return right - 1;
        }

        private String justify(int left, int right, String[] words, int maxWidth) {
            if (right - left == 0) return padResult(words[left], maxWidth);

            boolean isLastLine = right == words.length - 1;
            int numSpaces = right - left;
            int totalSpace = maxWidth - wordsLength(left, right, words);

            String space = isLastLine ? " " : blank(totalSpace / numSpaces);
            int remainder = isLastLine ? 0 : totalSpace % numSpaces;

            StringBuilder result = new StringBuilder();
            for (int i = left; i <= right; i++)
                result.append(words[i])
                    .append(space)
                    .append(remainder-- > 0 ? " " : "");

            return padResult(result.toString().trim(), maxWidth);
        }

        private int wordsLength(int left, int right, String[] words) {
            int wordsLength = 0;
            for (int i = left; i <= right; i++) wordsLength += words[i].length();
            return wordsLength;
        }

        private String padResult(String result, int maxWidth) {
            return result + blank(maxWidth - result.length());
        }

        private String blank(int length) {
            return new String(new char[length]).replace('\0', ' ');
        }

    }

// OJ: https://leetcode.com/problems/text-justification/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    vector<string> fullJustify(vector<string>& A, int maxWidth) {
        int i = 0, j = 0, N = A.size();
        vector<string> ans;
        while (j < N) {
            int width = A[j++].size();
            for (; j < N && width + A[j].size() + 1 <= maxWidth; ++j) {
                width += A[j].size() + 1;
            }
            int cnt = j - i, space = maxWidth - width + (cnt - 1), d, r;
            if (cnt > 1) {
                d = space / (cnt - 1);
                r = space % (cnt - 1);
            }
            ans.emplace_back();
            for (; i < j; ++i) {
                ans.back() += A[i];
                if (j == N || cnt == 1) { // if this is the last line or there is only one word in the line, the text is left-justified.
                    if (i < j - 1) ans.back() += ' ';
                    else {
                        while (ans.back().size() < maxWidth) ans.back() += ' ';
                    }
                } else if (i < j - 1) { // otherwise, it's full-justified. We only insert space between the words.
                    for (int k = 0; k < d; ++k) {
                        ans.back() += ' ';
                    }
                    if (r > 0) {
                        ans.back() += ' ';
                        --r;
                    }
                }
            }
        }
        return ans;
    }
};

class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        def partition(n, cnt):
            res = []
            base, mod = divmod(n, cnt)
            i = j = 0
            while i < cnt:
                t = [' ' * base]
                if j < mod:
                    t.append(' ')
                res.append(''.join(t))
                i, j = i + 1, j + 1
            return res

        ans = []
        i, n = 0, len(words)
        while i < n:
            t = []
            cnt = len(words[i])
            t.append(words[i])
            i += 1
            while i < n and cnt + 1 + len(words[i]) <= maxWidth:
                cnt += 1 + len(words[i])
                t.append(words[i])
                i += 1
            if i == n or len(t) == 1:
                # this is the last line or only one word in a line
                left = ' '.join(t)
                right = ' ' * (maxWidth - len(left))
                ans.append(left + right)
                if i == n:
                    break
                continue
            words_width = cnt - len(t) + 1
            space_width = maxWidth - words_width
            spaces = partition(space_width, len(t) - 1)
            sb = [t[0]]
            for j in range(len(t) - 1):
                sb.append(spaces[j])
                sb.append(t[j + 1])
            ans.append(''.join(sb))
        return ans

############

class Solution(object):
  def fullJustify(self, words, maxWidth):
    """
    :type words: List[str]
    :type maxWidth: int
    :rtype: List[str]
    """
    ans = []
    line = []
    lens = map(len, words)
    idx = 0
    curLen = 0
    while idx < len(words):
      if curLen == 0:
        curLen = lens[idx]
      else:
        curLen += lens[idx] + 1
      line.append(words[idx])
      idx += 1
      if curLen > maxWidth:
        curLen = 0
        line.pop()
        idx -= 1
        if len(line) == 1:
          ans.append(line[0] + " " * (maxWidth - len(line[0])))
          line = []
          continue
        spaces = maxWidth - sum(map(len, line))
        avgSpace = spaces / (len(line) - 1)
        extraSpace = spaces % (len(line) - 1)
        res = ""
        for i in range(0, len(line)):
          res += line[i]
          if i < len(line) - 1:
            res += " " * (avgSpace + (extraSpace > 0))
            extraSpace -= 1
        ans.append(res)
        line = []
      elif idx == len(words):
        res = ""
        for i in range(0, len(line)):
          res += line[i]
          if i < len(line) - 1:
            res += " "
        res += " " * (maxWidth - len(res))
        ans.append(res)
    return ans

68 - Text Justification

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions