master
1<<-DOC
2Given an array of words and a length l, format the text such that each line has exactly l characters
3and is fully justified on both the left and the right.
4Words should be packed in a greedy approach; that is,
5pack as many words as possible in each line.
6Add extra spaces when necessary so that each line has exactly l characters.
7
8Extra spaces between words should be distributed as evenly as possible.
9If the number of spaces on a line does not divide evenly between words,
10the empty slots on the left will be assigned more spaces than the slots on the right.
11For the last line of text and lines with one word only,
12the words should be left justified with no extra space inserted between them.
13
14Example
15
16For
17words = ["This", "is", "an", "example", "of", "text", "justification."]
18and l = 16, the output should be
19
20textJustification(words, l) = ["This is an",
21 "example of text",
22 "justification. "]
23Input/Output
24
25[time limit] 4000ms (rb)
26[input] array.string words
27
28An array of words. Each word is guaranteed not to exceed l in length.
29
30Guaranteed constraints:
311 ≤ words.length ≤ 150,
320 ≤ words[i].length ≤ l.
33
34[input] integer l
35
36The length that all the lines in the output array should be.
37
38Guaranteed constraints:
391 ≤ l ≤ 60.
40
41[output] array.string
42
43The formatted text as an array containing lines of text, with each line having a length of l.
44DOC
45describe "text_justification" do
46 def next_line(words, length)
47 line = []
48 line_length = 0
49
50 until words.empty?
51 word = words.shift
52 required_spaces = line.size
53 if line_length + word.size + required_spaces <= length
54 line.push(word)
55 line_length += word.size
56 else
57 words.unshift(word)
58 break
59 end
60 end
61 [length - line_length, line]
62 end
63
64 def pad_right(words, spaces)
65 return words.join(' ') if spaces == 0
66
67 before_spaces = words.map(&:size).inject(0, :+)
68 words_with_spaces = words.join(' ')
69 after_spaces = words_with_spaces.size
70 added_spaces = after_spaces - before_spaces
71 words_with_spaces + (" " * (spaces - added_spaces))
72 end
73
74 def pad_center(words, spaces)
75 return pad_right(words, spaces) if words.size == 1
76
77 until spaces <= 0
78 (words.size - 1).times do |n|
79 words[n] << " "
80 spaces -= 1
81 break if spaces == 0
82 end
83 end
84 words.join
85 end
86
87 def text_justification(words, length)
88 lines = []
89 until words.empty?
90 spaces, line = next_line(words, length)
91 right = words.empty? || line.size == 1
92 lines.push(right ? pad_right(line, spaces) : pad_center(line, spaces))
93 end
94 lines
95 end
96
97 def compute_cost(words, length)
98 cost_matrix = [words.size]
99 num_words = words.size
100 0.upto(num_words - 1) do |i|
101 cost_matrix[i] = [words.size]
102 (i).upto(num_words - 1) do |j|
103 candidates = words[i..j]
104 cost = length - (candidates.sum(&:size) + candidates.size - 1)
105 cost = cost >= 0 ? cost = cost ** 2 : Float::INFINITY
106 cost_matrix[i][j] = cost
107 end
108 end
109 cost_matrix
110 end
111
112 def dp_text_justification(words, length)
113 cost_matrix = compute_cost(words, length)
114 min_cost = []
115 final_result = []
116 i = j = words.size - 1
117 while i > -1
118 cost = cost_matrix[i][j]
119 if Float::INFINITY == cost
120 # check at what point we split it.
121 0.upto(j) do |jj|
122 next unless cost_matrix[i][j - jj]
123 next unless min_cost[j - jj + 1]
124 next_cost = cost_matrix[i][j - jj] + min_cost[j - jj + 1]
125 if next_cost < cost
126 cost = next_cost
127 min_cost[i] = cost
128 final_result[i] = j - jj + 1
129 end
130 end
131 j = words.size - 1
132 else
133 min_cost[i] = cost
134 final_result[i] = words.size
135 end
136 i -= 1
137 end
138
139 lines = []
140 n = 0
141 index = 0
142 loop do
143 take = final_result[n] - index
144 lines[index] = []
145 take.times do
146 lines[index] << words.shift
147 end
148 if words.empty?
149 lines[index] = pad_right(lines[index].compact, length - lines[index].compact.sum(&:size))
150 else
151 lines[index] = pad_center(lines[index].compact, length - lines[index].compact.sum(&:size))
152 end
153 n = final_result[n]
154 index += 1
155 break if words.empty?
156 end
157 lines
158 end
159
160 [
161 { words: ["Tushar", "Roy", "likes", "to", "code"], l: 10, expected: ["Tushar ", "Roy likes", "to code "] },
162 ].each do |x|
163 it do
164 result = dp_text_justification(x[:words], x[:l])
165 expect(result).to contain_exactly(*x[:expected])
166 end
167 end
168
169 [
170 { words: ["This", "is", "an", "example", "of", "text", "justification."], l: 16, expected: ["This is an", "example of text", "justification. "]},
171 { words: ["Two", "words."], l: 11, expected: ["Two words. "] },
172 { words: ["Two", "words."], l: 10, expected: ["Two words."] },
173 { words: ["Two", "words."], l: 9, expected: ["Two ", "words. "] },
174 { words: ["Looks", "like", "it", "can", "be", "a", "tricky", "test"], l: 25, expected: ["Looks like it can be a", "tricky test "] },
175 { words: ["a", "b", "b", "longword"], l: 8, expected: ["a b b", "longword"] },
176 { words: ["vba", "gaff", "ye", "gs", "cthj", "hf", "vetjj", "jm", "k", "f", "cgbf", "zzz"], l: 8, expected: ["vba gaff", "ye gs", "cthj hf", "vetjj jm", "k f cgbf", "zzz "] },
177 { words: ["Given", "an", "array", "of", "words", "and", "a", "length"], l: 9, expected: ["Given an", "array of", "words and", "a length "] },
178 { words: ["Extra", "spaces", "between", "words", "should", "be", "distributed", "as", "evenly", "as", "possible"], l: 20, expected: ["Extra spaces between", "words should be", "distributed as", "evenly as possible "] },
179 { words: [""], l: 2, expected: [" "] },
180 { words: ["a"], l: 1, expected: ["a"] },
181 { words: ["a"], l: 2, expected: ["a "] },
182 { words: ["a", "b", "c", "d", "e"], l: 1, expected: ["a", "b", "c", "d", "e"] },
183 { words: ["a", "b", "c", "d", "e"], l: 3, expected: ["a b", "c d", "e "] },
184 ].each do |x|
185 it do
186 result = text_justification(x[:words], x[:l])
187 expect(result).to contain_exactly(*x[:expected])
188 end
189 end
190end