WordWrap

SRM 186 · 2004-03-13 · by Eeyore

SRM 186 · 2004-03-13 · by Eeyore · String Manipulation

Show categories

Class Name: WordWrap

Return Type: String[]

Method Name: justify

Arg Types: (vector<string>, int)

Problem Statement

Some text editors, such as vi, model the user's document as a sequence of lines containing a variable number of characters. Because the human eye prefers to read lines of equal length, such editors typically supply a function that will adjust the lines to make them fit within a column of fixed width. This process is called justification. (Other editors, such as OpenOffice.org, will justify lines on the fly.)

Your job is to write a justifier for a simplified piece of text. You are given a String[], lines, each element of which is a single line consisting of tokens separated by single spaces. For the present purposes, a token is a sequence of lowercase alphabetical characters. You are to return a String[] containing the same tokens in the same order and still separated by single spaces, distributed in such a way that no line exceeds the desired column width, which is specified by the int columnWidth. Within these constraints, you should put as many tokens as possible in the first line, then as many as possible in the second, and so on.

Note that tokens must not be split between consecutive lines, and that the number of lines in the result may differ from that in the input. The resulting lines must contain tokens separated by single spaces, without extraneous spaces at the beginning or end of a line, akin to the input. No input token will be longer than the column width.

Constraints

lines contains between 1 and 50 elements, inclusive
each element of lines is between 1 and 50 characters long, inclusive
in each element of lines, only the space character (' ') and the lowercase alphabetical characters ('a' through 'z') are allowed
in each element of lines, neither the first nor last character may be a space
in each element of lines, there may not be two or more consecutive spaces
columnWidth is between 1 and 50, inclusive
in each element of lines, no sequence of alphabetic characters is more than columnWidth characters long

Examples

{"now is the time for all good men",
 "to come to the aid of their country"}
20
Returns: { "now is the time for",  "all good men to come",  "to the aid of their",  "country" }

Token order is preserved in the result, but no line exceeds 20 characters in length.

{"now",
 "is the time for",
 "all",
 "good",
 "men",
 "to",
 "come to the aid",
 "of",
 "their",
 "country"}
20
Returns: { "now is the time for",  "all good men to come",  "to the aid of their",  "country" }

Each line is made as long as possible without exceeding the column width.

{"four score and seven years ago", 
 "our fathers brought forth",
 "upon this continent",
 "a new nation",
 "conceived in liberty", 
 "and dedicated to the proposition", 
 "that all men are created",
 "equal"}
50
Returns: { "four score and seven years ago our fathers brought",  "forth upon this continent a new nation conceived",  "in liberty and dedicated to the proposition that",  "all men are created equal" }

{"th e ow l an d th e pu ss yc at",
 "we nt to se a",
 "on a be au ti fu l pe a gr ee n bo at"}
4
Returns: { "th e",  "ow l",  "an d",  "th e",  "pu",  "ss",  "yc",  "at",  "we",  "nt",  "to",  "se a",  "on a",  "be",  "au",  "ti",  "fu l",  "pe a",  "gr",  "ee n",  "bo",  "at" }

{"th e ow l an d th e pu ss yc at",
 "we nt to se a",
 "on a be au ti fu l pe a gr ee n bo at"}
2
Returns: { "th",  "e",  "ow",  "l",  "an",  "d",  "th",  "e",  "pu",  "ss",  "yc",  "at",  "we",  "nt",  "to",  "se",  "a",  "on",  "a",  "be",  "au",  "ti",  "fu",  "l",  "pe",  "a",  "gr",  "ee",  "n",  "bo",  "at" }

Submissions are judged against all 118 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class WordWrap with a public method vector<string> justify(vector<string> lines, int columnWidth) · 118 test cases · 2 s / 256 MB per case