Problem Description
Given a string s, where words are separated by a single space, print the words vertically. Each vertical column should represent the characters from the corresponding positions in each word. If a word is shorter than the longest word, fill in with spaces but remove trailing spaces in the final output.
Key Insights
- Split the input string into individual words.
- Determine the maximum word length.
- Construct vertical columns by iterating column-wise over the words.
- Fill with spaces when a word is too short.
- Trim any trailing spaces from each vertical column string.
Space and Time Complexity
Time Complexity: O(n * m), where n is the number of words and m is the length of the longest word. Space Complexity: O(n * m) for storing the output vertical strings.
Solution
We first split the input string into words. By determining the maximum length among these words, we understand the number of vertical columns needed. For each column index, iterate through each word: if the word has a character at that index, include it; otherwise, add a space. After constructing each vertical string, remove any trailing spaces before appending it to the result. Data structures used include arrays (or lists) for storing words and the resulting vertical strings. The algorithm mainly uses a double loop: one for the column iteration up to the maximum word length, and one for iterating over the words.