Author: Neel Shah
Tester: Shivam Pawase
Editorialist: Shivanee Jaiswal
DIFFICULTY
Easy - Medium
PRE-REQUISITES
None
PROBLEM
You are given a line containing x words which you have to justify such that each line contains m characters including the white-spaces.
The lines should be flushed left as well as right (i.e the first and last character of a line should not be a white-space).
The extra white-spaces left out of the m characters per line should be distributed
in that line one by one such that the first extra space goes between the two words such that the sum of lengths of the two words is the largest; followed by the next space going between the 2nd longest pair of words and so on.
If the spaces are left over after one round of distribution the same process is repeated
until the line is m characters long.
EXPLANATION
This problem can be solved by maintaining a list of words, such that those words along with the minimal one whitespace between them can fit into one line, of the specified width. Here’s the sample code for the same -
currl = 0
totwrds = [ ]
currwrds = [ ]
for i in range(nwrd):
currl += len(words[i])
currl += 1
if currl <= lim:
currwrds.append(words[i])
elif (currl-1) == lim:
currwrds.append(words[i])
totwrds.append(currwrds[:])
currwrds = [ ]
currl = 0
else:
totwrds.append(currwrds[:])
currwrds = [ ]
currl = len(words[i])
currl += 1
currwrds.append(words[i])
Next, we need to make a list, where each element is a pair. This list will be used to track and rank whitespaces, according to the length of the words that wrap around it. Also, the second index, in the pair will be the index of the whitespace from the left. We sort this list, such that the lengths are sorted in descending order, and indices in ascending. So, either one can use a custom comparing function here, or use a little trick and make the lengths negative, so the highest length, will be highest negative number, and hence lowest.
So, the default ascending sort works.
When all whitespaces are ranked and sorted by size, we go ahead and distribute them in a cyclic one by one order. The code for the distribution of white space is as follows -
whitespaces = []
for line in totwrds:
if len(line) > 1:
whitespace = []
totallen = 0
for i in range(len(line)-1):
totallen += len(line[i])
whitespace.append([-len(line[i])-len(line[i+1]),i])
totallen += len(line[-1])
whitespace.sort()
needed = lim - totallen
numwhite = len(whitespace)
mini = needed//numwhite
extra = needed%numwhite
finwhitespace = [0]*numwhite
for i in whitespace:
finwhitespace[i[1]] = mini
if extra > 0:
extra -= 1
finwhitespace[i[1]] += 1
# print(finwhitespace)
whitespaces.append(finwhitespace)
else:
whitespaces.append([0])
Solution: