This post is completed by 1 user

  • 0
 Add to List
Hard

Text Justification Problem (OR Word Wrap Problem)

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 most space (between two 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. If any spaces are left (in case even distribution is not possible), add it to between first 2 words.
  8. Replace ‘@’ with spaces calculated in the step above.
  9. Make a recursive call for rest of the words (from step 2 to Step 8)
  10. See the code for better understanding.

Code:


Output:

This      is    a    text
justification  problem in
tutorial horizon

Reference- here

Also Read: