题目

标题和出处

标题：竖直打印单词

出处：1324. 竖直打印单词

难度

5 级

题目描述

要求

给你一个字符串 。请你按照单词在 中的出现顺序将它们全部竖直返回。

单词应该以字符串列表的形式返回，必要时用空格补位，但输出尾部的空格需要删除（不允许尾随空格）。

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

示例

示例 1：

输入：
输出：
解释：每个单词都应该竖直打印。

示例 2：

输入：
输出：
解释：题目允许使用空格补位，但不允许输出末尾出现空格。

示例 3：

输入：
输出：

数据范围

• 
• 仅含大写英文字母
• 题目数据保证两个单词之间只有一个空格

解法

思路和算法

由于题目要求竖直打印单词，因此首先需要得到每个单词。在 Java 中， 类型有 方法，将字符串根据指定的分隔符分隔成字符串数组。由于这道题中的两个单词之间只有一个空格，因此按照空格分隔字符串 得到的字符串数组即为单词数组。

竖直打印单词，得到的字符串列表的列数等于单词数量，行数等于最大单词长度，因此需要遍历单词数组，得到最大单词长度，然后创建 类型的数组 ，数组长度为最大单词长度，用于存储竖直打印单词的结果。

得到最大单词长度和创建 类型的数组 之后，第二次遍历单词数组，对于每个单词，进行如下操作：

1. 从左到右遍历该单词，从上到下遍历数组 ，将该单词的每个字母依次拼接到数组 的每一行；
2. 如果该单词的长度小于最大单词长度，则对于数组 中的剩余行，每行拼接一个空格。

遍历结束之后，数组 存储了竖直打印单词的结果，此时每一行的尾部可能有空格，由于题目要求输出尾部的空格需要删除，因此还需要删除数组 每一行尾部的空格。

删除尾部空格的直观的做法是对数组 的每一行反向遍历，将该行末尾的空格删除。注意到最后一列有字母的行不可能有尾部的空格，而最后一列对应单词数组的最后一个单词，因此最后一列有字母的行数即为最后一个单词的长度，在删除尾部空格时可以跳过最后一列有字母的行。

例如，，数组 有 行，最后一个单词 长度为 ，因此数组 的前 行没有尾部的空格，只要对后 行删除尾部的空格。如下图所示，红色的位置表示需要删除的尾部的空格。

删除尾部空格之后，将数组 的每一行添加到结果列表即可。

代码

class Solution {
    public List<String> printVertically(String s) {
        String[] array = s.split(" ");
        int maxLength = 0;
        for (String word : array) {
            maxLength = Math.max(maxLength, word.length());
        }
        StringBuffer[] sb = new StringBuffer[maxLength];
        for (int i = 0; i < maxLength; i++) {
            sb[i] = new StringBuffer();
        }
        for (String word : array) {
            int length = word.length();
            for (int i = 0; i < length; i++) {
                sb[i].append(word.charAt(i));
            }
            for (int i = length; i < maxLength; i++) {
                sb[i].append(' ');
            }
        }
        int lastLength = array[array.length - 1].length();
        for (int i = maxLength - 1; i >= lastLength; i--) {
            int index = sb[i].length() - 1;
            while (index >= 0 && sb[i].charAt(index) == ' ') {
                sb[i].deleteCharAt(index);
                index--;
            }
        }
        List<String> list = new ArrayList<String>();
        for (int i = 0; i < maxLength; i++) {
            list.add(sb[i].toString());
        }
        return list;
    }
}

复杂度分析

• 时间复杂度：#card=math&code=O%28nl%29&id=qyH0B)，其中 是字符串 的单词数， 是字符串 的最大单词长度。
  • 需要遍历字符串数组两次，时间复杂度是 #card=math&code=O%28n%29&id=NqVCD)；
  • 拼接数组 的时间复杂度是 #card=math&code=O%28nl%29&id=GnBGE)；
  • 将数组 的每一行添加到结果列表的时间复杂度是 #card=math&code=O%28nl%29&id=jvsfQ)。
• 空间复杂度：#card=math&code=O%28nl%29&id=wAM39)，其中 是字符串 的单词数， 是字符串 的最大单词长度。需要额外创建一个 类型的数组用于存储竖直打印单词的结果。由于 Java 中的 类型的对象不可变，因此空间复杂度至少为 #card=math&code=O%28nl%29&id=MDAIW)。