题目描述

给你一个字符串 s。请你按照单词在 s 中的出现顺序将它们全部竖直返回。
单词应该以字符串列表的形式返回，必要时用空格补位，但输出尾部的空格需要删除（不允许尾随空格）。

每个单词只能放在一列上，每一列中也只能有一个单词。

样例

输入：s = "HOW ARE YOU"
输出：["HAY","ORO","WEU"]
解释：每个单词都应该竖直打印。 
 "HAY"
 "ORO"
 "WEU"
示例 2：

输入：s = "TO BE OR NOT TO BE"
输出：["TBONTB","OEROOE","   T"]
解释：题目允许使用空格补位，但不允许输出末尾出现空格。
"TBONTB"
"OEROOE"
"   T"
示例 3：

输入：s = "CONTEST IS COMING"
输出：["CIC","OSO","N M","T I","E N","S G","T"]

限制

• 1 <= s.length <= 200
• s 仅含大写英文字母。
• 题目数据保证两个单词之间只有一个空格。

算法

(模拟) $O(L)$

1. 将每个单词按空格拆分，并存入二维数组。
2. 按列遍历这个二维数组，记录答案即可。

时间复杂度

• 每个位置的字符仅被遍历常数次，故时间复杂度为 $O(L)$。

空间复杂度

• 需要额外 $O(L)$ 的空间存放二维数组和答案。

C++ 代码

class Solution {
public:
    vector<string> printVertically(string s) {
        vector<string> v;
        string t;
        int m = 0;
        for (int i = 0; i <= s.length(); i++) {
            if (i == s.length() || s[i] == ' ') {
                if (m < t.length())
                    m = t.length();
                v.push_back(t);
                t.clear();
            } else {
                t += s[i];
            }
        }

        vector<string> ans;
        for (int j = 0; j < m; j++) {
            for (int i = 0; i < v.size(); i++)
                if (j < v[i].length())
                    t += v[i][j];
                else
                    t += ' ';

            while (t.back() == ' ')
                t.pop_back();
            ans.push_back(t);
            t.clear();
        }

        return ans;
    }
};