LeetCode 1324. 竖直打印单词-白红宇

LeetCode 1324. 竖直打印单词

阅读量：2008 次

发布时间：2019-04-28

本文共 1490 字，大约阅读时间需要 4 分钟。

1. 题目

给你一个字符串 s。请你按照单词在 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 <= 200s 仅含大写英文字母。题目数据保证两个单词之间只有一个空格。

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

2. 解题

先把单词的末尾加个空格，方便找到字符串中每个单词的起始位置

对每个单词的起始位置处的字符拼起来，遇到空格的下标置为-1，否则+1

生成的字符串，删除结尾的空格，若为空，结束查找

class Solution {
   public:    vector
   
     printVertically(string s) {
       	vector
    
      idx;        s.push_back(' ');    	int i, n = s.size();    	char prev = ' ';    	for(i = 0; i < n; ++i)    	{
       		if(prev==' ' && s[i] != ' ')    			idx.push_back(i);//每个单词起点    		prev = s[i];    	}    	vector
     
       ans;    	string str;    	while(1)    	{
       		str = "";    		for(i = 0; i < idx.size(); ++i)    		{
       			if(idx[i] != -1)//下标不为-1    			{
       				str += s[idx[i]++];//拼接字符，下标+1    				if(s[idx[i]] == ' ')//+1后为空字符    					idx[i] = -1;//置为-1    			}    			else    				str += ' ';//为-1的话，补空格    		}    		while(!str.empty() && str.back()==' ')    			str.pop_back();//删除尾部空格    		if(str == "")    			break;//字符串空，说明，全部到达末尾，结束    		else    			ans.push_back(str);    	}    	return ans;    }};