Given a string s. Return all the words vertically in the same order in which they appear in s.
Words are returned as a list of strings, complete with spaces when is necessary. (Trailing spaces are not allowed).
Each word would be put on only one column and that in one column there will be only one word.
Example 1:
Input: s = "HOW ARE YOU" Output: ["HAY","ORO","WEU"] Explanation: Each word is printed vertically. "HAY" "ORO" "WEU"
Example 2:
Input: s = "TO BE OR NOT TO BE" Output: ["TBONTB","OEROOE"," T"] Explanation: Trailing spaces is not allowed. "TBONTB" "OEROOE" " T"
Example 3:
Input: s = "CONTEST IS COMING" Output: ["CIC","OSO","N M","T I","E N","S G","T"]
Constraints:
1 <= s.length <= 200s contains only upper case English letters.Problem Overview: Given a sentence containing multiple words separated by spaces, you need to print the words vertically. Characters in the same column across words form a new string. Missing characters are treated as spaces, but trailing spaces in each vertical word must be removed.
Approach 1: Column-wise Iteration (O(n * m) time, O(n * m) space)
Split the input string into words and determine the maximum word length. Treat each character index as a column. For column i, iterate through every word and append the character at position i if it exists; otherwise append a space. After constructing the column string, trim trailing spaces before adding it to the result. This approach directly simulates vertical printing using simple iteration over the array of words and character positions. The logic stays straightforward and avoids building an intermediate grid.
Approach 2: Matrix Transposition Approach (O(n * m) time, O(n * m) space)
Create a 2D matrix where each row represents a word and each column represents a character position up to the longest word length. Fill the matrix with characters from each word, padding missing positions with spaces. After building the matrix, transpose it by reading column-by-column to construct vertical strings. Trim trailing spaces before adding each result string. This method models the problem as a grid transformation, similar to matrix operations commonly used in simulation and string manipulation problems.
Recommended for interviews: The column-wise iteration approach is usually preferred. It avoids explicitly storing a full matrix and directly constructs the result with simple loops. Interviewers expect you to recognize that vertical output corresponds to iterating character positions across words. The matrix approach still demonstrates clear thinking and works well as a conceptual stepping stone.
This approach involves creating a list of strings, where each string represents a vertical column. First, split the string by spaces to get the words. Then calculate the maximum word length. For each column index, iteratively build the column string by taking the character from each word at that column index, if it exists, or space if it doesn’t. Trim trailing spaces from each of column strings.
This solution uses the strtok function to split the input string into words. It stores the words in an array and identifies the longest word's length. The solution then iterates over each character index up to that length, constructing a column by pulling characters from each word. If a word is shorter than the current column index, a space is added. Finally, each column string is printed after trimming trailing spaces.
Time complexity: O(n * m), where n is the maximum word length and m is the number of words. Space complexity: O(n * m) as well, assuming all strings have been stored in memory.
Create a matrix of characters where each row represents a word and characters are positioned according to their input order. Then perform a transposition of this matrix, which swaps rows and columns, producing vertical words as rows. Trim the trailing spaces from these rows to complete the solution.
Similar to our previous C implementation, this solution also calculates the maximum word length to determine the number of columns. For each index up to the maximum length, the code assembles and prints a vertical line by drawing from each word, using spaces where necessary. The main difference is in structuring logic towards a matrix analogy concept, emphasizing the transposition of words.
Time complexity: O(n * m), where n is the maximum length of words and m is the number of words. Space complexity: O(n * m).
| Approach | Complexity |
|---|---|
| Column-wise Iteration Approach | Time complexity: O(n * m), where n is the maximum word length and m is the number of words. Space complexity: O(n * m) as well, assuming all strings have been stored in memory. |
| Matrix Transposition Approach | Time complexity: O(n * m), where n is the maximum length of words and m is the number of words. Space complexity: O(n * m). |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Column-wise Iteration | O(n * m) | O(n * m) | Best general solution. Directly builds vertical strings without creating a full matrix. |
| Matrix Transposition | O(n * m) | O(n * m) | Useful when visualizing the problem as a grid or practicing matrix transformation techniques. |
Microsoft Coding Interview Question - Print Words Vertically (LeetCode) • AlgosWithMichael • 4,458 views views
Watch 5 more video solutions →Practice Print Words Vertically with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor