字符串题目:竖直打印单词

文章目录

题目

标题和出处

标题:竖直打印单词

出处: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 之后,第二次遍历单词数组,对于每个单词,进行如下操作:

  1. 从左到右遍历该单词,从上到下遍历数组 sb \textit{sb} sb,将该单词的每个字母依次拼接到数组 sb \textit{sb} sb 的每一行;

  2. 如果该单词的长度小于最大单词长度,则对于数组 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)。

上一篇:递归解数独


下一篇:链表题目:反转链表