题目描述

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/print-words-vertically
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

样例

示例 1：

输入：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 仅含大写英文字母。
题目数据保证两个单词之间只有一个空格。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/print-words-vertically
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

算法

(模拟) $O(n)$

题意是把几个单词纵向组合在一起然后返回。我们首先要把单词分隔开，然后按照规律组合在一起。
先遍历字符串，然后就可以把字符串分成几个单词了。找到这些单词的最大长度，这个最大长度，就是要返回的字符串数组的长度。
可以手动模拟一下，题意的要求是返回的字符串数组中的字符串，可以有前缀0用来占位但是不能有后缀0。因为这个规则，我们可以从后向前遍历拆分好的单词数组，这样我们就可以直到是否需要加空格。以下用“contest is coming”举例。
“contest is coming” => “contest”, “is”, “coming”=>最大长度 m = 7，答案字符串数组的长度就是7
第一步，单词coming,coming的长度是6，把每个单词逐个接到答案字符串数组中的7个字符串中。因为前面没有单词，所以第七个字符串不需要加空格。
第二步，单词is，长度为2，因为前面coming的长度为6，所以我们要在答案字符串数组中的第3~6个单词加一个空格。
第三步，单词contest，长度为7，按照顺序接到答案字符串中的7个字符串中。过程如下图

可以看到，如果我们遍历单词的长度l小于m，并且第l~m个字符串已经有字母的时候，我们就需要加空格对齐。
另外，注意接入字母的顺序，因为我们是从最后一个单词开始遍历，所以我们要把后面的字母接入到已经存在的字母的前面。

C++ 代码

class Solution {
public:
    vector<string> printVertically(string s) {
        string cur = "";
        vector<string> words;
        for(int i = 0; i <= s.size(); i++){//将字符串拆分成单词。
            if(i == s.size() || s[i] == ' '){
                words.push_back(cur);
                cur = "";
            }
            else cur += s[i];
        }
        int m = -1;
        for(auto word : words) m = max(m, (int)word.size());//求单词的最大长度
        vector<string> res(m, "");//答案数组
        for(int i = words.size() - 1; ~i; i -- ){//从后向前遍历单词
            int l = words[i].size();
            for(int j = 0; j<l; j ++ )  //处理0~l
                res[j] = words[i][j] + res[j];
            for(int j = l; j<m; j ++ )
                if(res[j].size()) res[j] = " " + res[j];//处理l~m，如果之前存在字符，则加空格对齐。
        }
        return res;
    }
};