Print Words Vertically
Medium · Matrix · Array · String · Simulation
Problem
You are given a string s of upper-case words separated by single spaces. Write the words vertically: word k runs down column k, one letter per row, every word starting in the top row.
Return the rows, top to bottom, as a list of strings. Where a word is too short to reach a row, its cell in that row is a space, but each row has its trailing spaces removed.
Examples
Input: s = "CAT DOG" Output: ["CD","AO","TG"]
Column 0 spells CAT and column 1 spells DOG, so the rows are CD, AO and TG.
Input: s = "GO HOME NOW" Output: ["GHN","OOO"," MW"," E"]
GO ends after two rows, so rows 2 and 3 start with a space; NOW ends after three, and row 3 loses its trailing space.
Input: s = "A BIG" Output: ["AB"," I"," G"]
A is used up after the top row, so the rows below start with a space.
Constraints
- 1 <= len(s) <= 200
- s consists of upper-case English letters and spaces
- Words are separated by exactly one space, with no leading or trailing space
Approaches
- Baseline: rescan the sentence for every row — time O(h · |s|), space O(h · W) for the answer
Follow-up
Can you go the other way, rebuilding the sentence from the rows? Or align the words at the bottom instead of the top? Both are use cases below.
Related problems
Start free on Cariara · Coding problems · System design studio
