Question

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

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.

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 maxWidth characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does 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.

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

Constraints:

1 <= words.length <= 300
1 <= words[i].length <= 20
words[i] consists of only English letters and symbols.
1 <= maxWidth <= 100
words[i].length <= maxWidth

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

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', ' ');
        }

    }

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

class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> ans = new ArrayList<>();
        int n = words.length;
        for (int i = 0; i < n;) {
            List<String> t = new ArrayList<>();
            int cnt = words[i].length();
            t.add(words[i++]);
            while (i < n && cnt + 1 + words[i].length() <= maxWidth) {
                cnt += 1 + words[i].length();
                t.add(words[i++]);
            }
            if (i == n || t.size() == 1) {
                // this is the last line or only one word in a line
                String left = String.join(" ", t);
                String right = " ".repeat(maxWidth - left.length());
                ans.add(left + right);
                if (i == n) {
                    break;
                }
                continue;
            }

            int wordsWidth = cnt - t.size() + 1;
            int spaceWidth = maxWidth - wordsWidth;
            List<String> spaces = partition(spaceWidth, t.size() - 1);
            StringBuilder sb = new StringBuilder(t.get(0));
            for (int j = 0; j < t.size() - 1; ++j) {
                sb.append(spaces.get(j));
                sb.append(t.get(j + 1));
            }
            ans.add(sb.toString());
        }
        return ans;
    }

    private List<String> partition(int n, int cnt) {
        List<String> ans = new ArrayList<>();
        int base = n / cnt;
        int mod = n % cnt;
        for (int i = 0, j = 0; i < cnt; ++i, ++j) {
            StringBuilder sb = new StringBuilder(" ".repeat(base));
            if (j < mod) {
                sb.append(' ');
            }
            ans.add(sb.toString());
        }
        return ans;
    }
}

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

'''
>>> 17 % 3
2
>>> divmod(17,3)
(5, 2)
'''

'''
>>> ['This', 'is', 'an']
['This', 'is', 'an']
>>> t = ['This', 'is', 'an']
>>> spaces = ['    ', '    ']

# note: here j starts from 0
>>> for j, word in enumerate(t[1:]):
...     print(j)
...     print(word)
...
0
is
1
an
'''

class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        def partition(n, cnt):
            base, mod = divmod(n, cnt)
            res = [f"{' ' * (base + (i < mod))}" for i in range(cnt)]
            return res

        ans = []
        i, n = 0, len(words)
        while i < n: # one line per iteration
            t = [words[i]]
            cnt = len(words[i])
            i += 1 # move to next word
            while i < n and cnt + 1 + len(words[i]) <= maxWidth: # greedy search for one line
                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 (super-long) word in a line
                left = ' '.join(t)
                right = ' ' * (maxWidth - len(left))
                ans.append(f"{left}{right}")
                continue # so i != n , so only one word, no need to add spaces. 
                         # e.g. a word with the same length as maxWidth, 
                         # or, e.g. the 2nd word is super long and cannot fit in current line
                # if i==n, then will not enter next while
            words_width = cnt - (len(t) - 1) # pure words total length, with no spaces
                                             # spaces in-between these words in t[]: len(t) - 1
            space_width = maxWidth - words_width
            spaces = partition(space_width, len(t) - 1)
            sb = [t[0]] # 1st word of this line, no space before it
            for j, word in enumerate(t[1:]): # last word has no following space
                sb.append(spaces[j])
                sb.append(word)
            ans.append(''.join(sb))
        return ans

###########

class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        left = 0
        result = []
        
        while left < len(words):
            right = self.findRight(left, words, maxWidth)
            result.append(self.justify(left, right, words, maxWidth))
            left = right + 1
        
        return result
    
    def findRight(self, left, words, maxWidth):
        right = left
        word_length = len(words[right])
        
        while (right + 1) < len(words) and (word_length + 1 + len(words[right+1])) <= maxWidth:
            right += 1
            word_length += 1 + len(words[right])
        
        return right
    
    def justify(self, left, right, words, maxWidth):
        if right - left == 0:
            return self.padResult(words[left], maxWidth)
        
        is_last_line = (right == len(words) - 1)
        num_spaces = right - left
        total_space = maxWidth - self.wordsLength(left, right, words)
        
        space = " " if is_last_line else " " * (total_space // num_spaces)
        remainder = 0 if is_last_line else total_space % num_spaces
        
        result = ""
        for i in range(left, right):
            result += words[i]
            result += space
            if remainder > 0:
                result += " "
                remainder -= 1
        
        result += words[right]
        result += " " * (maxWidth - len(result))
        
        return result
    
    def wordsLength(self, left, right, words):
        words_length = 0
        for i in range(left, right+1):
            words_length += len(words[i])
        return words_length
    
    def padResult(self, result, maxWidth):
        return result + " " * (maxWidth - len(result))

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

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

func fullJustify(words []string, maxWidth int) []string {
	partition := func(n, cnt int) []string {
		var res []string
		base, mod := n/cnt, n%cnt
		for i, j := 0, 0; i < cnt; i, j = i+1, j+1 {
			t := strings.Repeat(" ", base)
			if j < mod {
				t += " "
			}
			res = append(res, t)
		}
		return res
	}

	var ans []string
	for i, n := 0, len(words); i < n; {
		t := []string{words[i]}
		cnt := len(words[i])
		i++
		for i < n && cnt+1+len(words[i]) <= maxWidth {
			cnt += 1 + len(words[i])
			t = append(t, words[i])
			i++
		}
		if i == n || len(t) == 1 {
			left := strings.Join(t, " ")
			right := strings.Repeat(" ", maxWidth-len(left))
			ans = append(ans, left+right)
			if i == n {
				break
			}
			continue
		}
		wordsWidth := cnt - len(t) + 1
		spaceWidth := maxWidth - wordsWidth
		spaces := partition(spaceWidth, len(t)-1)
		sb := t[0]
		for j := 0; j < len(t)-1; j++ {
			sb += spaces[j] + t[j+1]
		}
		ans = append(ans, sb)
	}
	return ans
}

using System.Collections.Generic;
using System.Linq;
using System.Text;

public class Solution {
    public IList<string> FullJustify(string[] words, int maxWidth) {
        var result = new List<string>();
        var buffer = new List<string>();
        var sb = new StringBuilder();
        var len = 0;
        
        for (var i = 0; i < words.Length; ++i)
        {
            var newLen = words[i].Length + (len == 0 ? 0 : len + 1);
            if (newLen <= maxWidth)
            {
                buffer.Add(words[i]);
                len = newLen;
            }
            else
            {
                if (buffer.Count == 1)
                {
                    sb.Append(buffer[0]);
                    sb.Append(' ', maxWidth - buffer[0].Length);
                }
                else
                {
                    var spaceCount = maxWidth - len + buffer.Count - 1;
                    for (var j = 0; j < buffer.Count - 1; ++j)
                    {
                        sb.Append(buffer[j]);
                        var spaceToAdd = (spaceCount - 1) / (buffer.Count - j - 1) + 1;
                        sb.Append(' ', spaceToAdd);
                        spaceCount -= spaceToAdd;
                    }
                    sb.Append(buffer.Last());
                }
                result.Add(sb.ToString());
                buffer.Clear();
                buffer.Add(words[i]);
                sb.Clear();
                len = words[i].Length;
            }
        }
        
        if (buffer.Count > 0)
        {
            for (var j = 0; j < buffer.Count; ++j)
            {
                if (sb.Length > 0)
                {
                    sb.Append(' ');
                }
                sb.Append(buffer[j]);
            }
            if (sb.Length < maxWidth)
            {
                sb.Append(' ', maxWidth - sb.Length);
            }
            result.Add(sb.ToString());
        }
        
        return result;
    }
}

function fullJustify(words: string[], maxWidth: number): string[] {
    const ans: string[] = [];
    for (let i = 0, n = words.length; i < n; ) {
        const t: string[] = [words[i]];
        let cnt = words[i++].length;
        while (i < n && cnt + 1 + words[i].length <= maxWidth) {
            t.push(words[i]);
            cnt += 1 + words[i++].length;
        }
        if (i === n || t.length === 1) {
            const left: string = t.join(' ');
            const right: string = ' '.repeat(maxWidth - left.length);
            ans.push(left + right);
            continue;
        }
        const spaceWidth: number = maxWidth - (cnt - t.length + 1);
        const w: number = Math.floor(spaceWidth / (t.length - 1));
        const m: number = spaceWidth % (t.length - 1);
        const row: string[] = [];
        for (let j = 0; j < t.length - 1; ++j) {
            row.push(t[j]);
            row.push(' '.repeat(w + (j < m ? 1 : 0)));
        }
        row.push(t[t.length - 1]);
        ans.push(row.join(''));
    }
    return ans;
}

68 - Text Justification

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions