文章目录
题目
标题和出处
标题：竖直打印单词
出处：1324. 竖直打印单词
难度
5 级
题目描述
要求
给你一个字符串 s \texttt{s} s。请你按照单词在 s \texttt{s} s 中的出现顺序将它们全部竖直返回。
单词应该以字符串列表的形式返回，必要时用空格补位，但输出尾部的空格需要删除（不允许尾随空格）。
每个单词只能放在一列上，每一列中也只能有一个单词。
示例
示例 1：
输入：
s
=
"HOW
ARE
YOU"
\texttt{s = "HOW ARE YOU"}
s = "HOW ARE YOU"
输出：
["HAY","ORO","WEU"]
\texttt{["HAY","ORO","WEU"]}
["HAY","ORO","WEU"]
解释：每个单词都应该竖直打印。
"HAY"
\texttt{"HAY"}
"HAY"
"ORO"
\texttt{"ORO"}
"ORO"
"WEU"
\texttt{"WEU"}
"WEU"
示例 2：
输入：
s
=
"TO
BE
OR
NOT
TO
BE"
\texttt{s = "TO BE OR NOT TO BE"}
s = "TO BE OR NOT TO BE"
输出：
["TBONTB","OEROOE","
T"]
\texttt{["TBONTB","OEROOE"," T"]}
["TBONTB","OEROOE"," T"]
解释：题目允许使用空格补位，但不允许输出末尾出现空格。
"TBONTB"
\texttt{"TBONTB"}
"TBONTB"
"OEROOE"
\texttt{"OEROOE"}
"OEROOE"
"
T"
\texttt{" T"}
" T"
示例 3：
输入：
s
=
"CONTEST
IS
COMING"
\texttt{s = "CONTEST IS COMING"}
s = "CONTEST IS COMING"
输出：
["CIC","OSO","N
M","T
I","E
N","S
G","T"]
\texttt{["CIC","OSO","N M","T I","E N","S G","T"]}
["CIC","OSO","N M","T I","E N","S G","T"]
数据范围
- 1 ≤ s.length ≤ 200 \texttt{1} \le \texttt{s.length} \le \texttt{200} 1≤s.length≤200
- s \texttt{s} s 仅含大写英语字母
- 题目数据保证两个单词之间只有一个空格
解法
思路和算法
由于题目要求竖直打印单词，因此首先需要得到每个单词。在 Java 中， String \texttt{String} String 类型有 split \texttt{split} split 方法，将字符串根据指定的分隔符分隔成字符串数组。由于这道题中的两个单词之间只有一个空格，因此按照空格分隔字符串 s s s 得到的字符串数组即为单词数组。
竖直打印单词，得到的字符串列表的列数等于单词数量，行数等于最大单词长度，因此需要遍历单词数组，得到最大单词长度，然后创建 StringBuffer \texttt{StringBuffer} StringBuffer 类型的数组 sb \textit{sb} sb，数组长度为最大单词长度，用于存储竖直打印单词的结果。
得到最大单词长度和创建 StringBuffer \texttt{StringBuffer} StringBuffer 类型的数组 sb \textit{sb} sb 之后，第二次遍历单词数组，对于每个单词，进行如下操作：
-
从左到右遍历该单词，从上到下遍历数组 sb \textit{sb} sb，将该单词的每个字母依次拼接到数组 sb \textit{sb} sb 的每一行；
-
如果该单词的长度小于最大单词长度，则对于数组 sb \textit{sb} sb 中的剩余行，每行拼接一个空格。
遍历结束之后，数组 sb \textit{sb} sb 存储了竖直打印单词的结果，此时每一行的尾部可能有空格，由于题目要求输出尾部的空格需要删除，因此还需要删除数组 sb \textit{sb} sb 每一行尾部的空格。
删除尾部空格的直观的做法是对数组 sb \textit{sb} sb 的每一行反向遍历，将该行末尾的空格删除。注意到最后一列有字母的行不可能有尾部的空格，而最后一列对应单词数组的最后一个单词，因此最后一列有字母的行数即为最后一个单词的长度，在删除尾部空格时可以跳过最后一列有字母的行。
例如， s = “KNOWLEDGE IS POWER" s = \text{``KNOWLEDGE IS POWER"} s=“KNOWLEDGE IS POWER"，数组 sb \textit{sb} sb 有 9 9 9 行，最后一个单词 “POWER" \text{``POWER"} “POWER" 长度为 5 5 5，因此数组 sb \textit{sb} sb 的前 5 5 5 行没有尾部的空格，只要对后 4 4 4 行删除尾部的空格。如下图所示，红色的位置表示需要删除的尾部的空格。
删除尾部空格之后，将数组 sb \textit{sb} sb 的每一行添加到结果列表即可。
代码
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;
}
}
复杂度分析
-
时间复杂度： O ( n l ) O(nl) O(nl)，其中 n n n 是字符串 s s s 的单词数， l l l 是字符串 s s s 的最大单词长度。
- 需要遍历字符串数组两次，时间复杂度是 O ( n ) O(n) O(n)；
- 拼接数组 sb \textit{sb} sb 的时间复杂度是 O ( n l ) O(nl) O(nl)；
- 将数组 sb \textit{sb} sb 的每一行添加到结果列表的时间复杂度是 O ( n l ) O(nl) O(nl)。
-
空间复杂度： O ( n l ) O(nl) O(nl)，其中 n n n 是字符串 s s s 的单词数， l l l 是字符串 s s s 的最大单词长度。需要额外创建一个 StringBuffer \texttt{StringBuffer} StringBuffer 类型的数组用于存储竖直打印单词的结果。由于 Java 中的 String \texttt{String} String 类型的对象不可变，因此空间复杂度至少为 O ( n l ) O(nl) O(nl)。