Print Words Vertically - Video Solutions
Microsoft Coding Interview Question - Print Words Vertically (LeetCode)
Print Words Vertically - Video Solution
Watch 6 video solutions for Print Words Vertically, a medium level problem involving Array, String, Simulation. This walkthrough by AlgosWithMichael has 4,486 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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 <= 200scontains only upper case English letters.- It's guaranteed that there is only one space between 2 words.
Approach Overview
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.
Complexity Analysis
| 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. |