Medium

题目描述

给你一个字符串 s。请你按照字符串中出现的相同顺序，返回所有单词竖直排列的结果。

单词应该以字符串列表的形式返回，必要时用空格补全(不允许尾随空格)。 每个单词只能放在一列中，在一列中也只能有一个单词。

示例 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 仅含大写英文字母
  • 保证两个单词之间只有一个空格

解题思路

这道题要求我们将一行中的单词竖直排列输出。

核心思路：

  1. 分割字符串：首先将输入字符串按空格分割成单词数组
  2. 确定结果长度：结果数组的长度等于所有单词中最长单词的长度
  3. 逐行构建：对于结果的每一行，遍历所有单词，取对应位置的字符
  4. 处理边界：当某个单词长度不够时，用空格填充
  5. 去除尾随空格：每行构建完成后，需要移除末尾的空格

算法步骤：

  • 将字符串分割成单词数组
  • 找出最长单词的长度作为结果行数
  • 对于每一行，遍历所有单词的对应位置字符
  • 如果单词长度不够，则用空格补齐
  • 最后去除每行末尾的空格

这个解法的时间复杂度主要取决于字符总数，空间复杂度为结果存储空间。

代码实现

class Solution {
public:
    vector<string> printVertically(string s) {
        vector<string> words;
        stringstream ss(s);
        string word;
        
        // 分割字符串获取所有单词
        while (ss >> word) {
            words.push_back(word);
        }
        
        // 找到最长单词的长度
        int maxLen = 0;
        for (const string& w : words) {
            maxLen = max(maxLen, (int)w.length());
        }
        
        vector<string> result(maxLen);
        
        // 构建每一行
        for (int i = 0; i < maxLen; i++) {
            for (int j = 0; j < words.size(); j++) {
                if (i < words[j].length()) {
                    result[i] += words[j][i];
                } else {
                    result[i] += ' ';
                }
            }
            
            // 移除尾随空格
            while (!result[i].empty() && result[i].back() == ' ') {
                result[i].pop_back();
            }
        }
        
        return result;
    }
};

class Solution:
    def printVertically(self, s: str) -> List[str]:
        words = s.split()
        max_len = max(len(word) for word in words)
        result = []
        
        for i in range(max_len):
            row = ""
            for word in words:
                if i < len(word):
                    row += word[i]
                else:
                    row += " "
            
            # 移除尾随空格
            result.append(row.rstrip())
        
        return result

public class Solution {
    public IList<string> PrintVertically(string s) {
        string[] words = s.Split(' ');
        int maxLen = 0;
        
        // 找到最长单词的长度
        foreach (string word in words) {
            maxLen = Math.Max(maxLen, word.Length);
        }
        
        List<string> result = new List<string>();
        
        // 构建每一行
        for (int i = 0; i < maxLen; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < words.Length; j++) {
                if (i < words[j].Length) {
                    sb.Append(words[j][i]);
                } else {
                    sb.Append(' ');
                }
            }
            
            // 移除尾随空格
            result.Add(sb.ToString().TrimEnd());
        }
        
        return result;
    }
}

/**
 * @param {string} s
 * @return {string[]}
 */
var printVertically = function(s) {
    const words = s.split(' ');
    const maxLen = Math.max(...words.map(word => word.length));
    const result = [];
    
    for (let i = 0; i < maxLen; i++) {
        let row = '';
        for (let j = 0; j < words.length; j++) {
            if (i < words[j].length) {
                row += words[j][i];
            } else {
                row += ' ';
            }
        }
        
        // 移除尾随空格
        result.push(row.replace(/\s+$/, ''));
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)n 为字符串总长度，需要遍历所有字符
空间复杂度O(n)存储分割后的单词和结果数组