This post is completed by 1 user

  • 0
 Add to List
Hard

252. Text Justification Problem (OR Word Wrap Problem) - Leetcode 68

Objec­tive:  Given a list of words and length L. Format the words so that each line will have only L characters and fully justified (left and right justified).

Restrictions-

  • You need to fit as many as words in every line.
  • You are not allowed to split a word and put them in next line.
  • Pad extra spaces ‘ ‘ if needed so that each line has L characters.
  • Extra spaces between words should be distributed as evenly as possible. If even distribution is not possible then extra spaces will be assigned on the left slots more the slots on the right.
  • For the last line of text, it should be left-justified, and no extra space is inserted between words.

Assumption – Each word has length less than Length L.

Example:

String [] words = {"This", "is", "a", "text", "justification","problem","in","tutorial","horizon"};
int length = 20;

Output:
This   is   a   text
justification
problem  in tutorial
horizon

Approach: Recursion

Maintain an index which tracks the numbers of words already used (already justified)

  1. Say Length = L number of characters in each line.
  2. Start taking words into a new line.
  3. Keep track of number of characters adding to the new line.
  4. Add a special character (‘@’) after each word (later will replace by space ‘ ‘)
  5. Stop adding word to new line if Either adding new word will exceed the characters count in line from given length L Or characters count = Length L.
  6. Calculate the number of spaces needs to add to make the characters count to length L.
  7. Evenly distribute the spaces between the selected words from left to right, this way extra spaces (if any) will be at the left slots more than the right slots.
  8. Edge case - If line has only one word then all the remaining spaces will be added to the right side of the word.
  9. Edge case - If its a last line - do not add remaining spaces in between the words, add it at the end.
  10. Make a recursive call for rest of the words (from step 2 to Step 8)
  11. See the code for better understanding.

Output:

This      is    a    text
justification  problem in
tutorial horizon

Reference- LeetCode

Related Problems: