Skip to content

Latest commit

 

History

History
181 lines (145 loc) · 4.58 KB

File metadata and controls

181 lines (145 loc) · 4.58 KB

English Version

题目描述

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

解法

方法一:模拟

我们先将字符串 $s$ 按空格分割成单词数组 $words$,然后遍历单词数组,找出最长的单词长度 $n$

接下来我们从第 $1$ 到第 $n$ 个字符,分别从单词数组中取出对应的字符,如果当前单词长度不足,则用空格补齐,放到一个字符串 $t$ 中。最后将 $t$ 去掉末尾的空格,加入答案数组中即可。

时间复杂度 $O(m)$,空间复杂度 $O(m)$。其中 $m$ 为字符串 $s$ 的长度。

Python3

class Solution:
    def printVertically(self, s: str) -> List[str]:
        words = s.split()
        n = max(len(w) for w in words)
        ans = []
        for j in range(n):
            t = [w[j] if j < len(w) else ' ' for w in words]
            while t[-1] == ' ':
                t.pop()
            ans.append(''.join(t))
        return ans

Java

class Solution {
    public List<String> printVertically(String s) {
        String[] words = s.split(" ");
        int n = 0;
        for (var w : words) {
            n = Math.max(n, w.length());
        }
        List<String> ans = new ArrayList<>();
        for (int j = 0; j < n; ++j) {
            StringBuilder t = new StringBuilder();
            for (var w : words) {
                t.append(j < w.length() ? w.charAt(j) : ' ');
            }
            while (t.length() > 0 && t.charAt(t.length() - 1) == ' ') {
                t.deleteCharAt(t.length() - 1);
            }
            ans.add(t.toString());
        }
        return ans;
    }
}

C++

class Solution {
public:
    vector<string> printVertically(string s) {
        stringstream ss(s);
        vector<string> words;
        string word;
        int n = 0;
        while (ss >> word) {
            words.emplace_back(word);
            n = max(n, (int) word.size());
        }
        vector<string> ans;
        for (int j = 0; j < n; ++j) {
            string t;
            for (auto& w : words) {
                t += j < w.size() ? w[j] : ' ';
            }
            while (t.size() && t.back() == ' ') {
                t.pop_back();
            }
            ans.emplace_back(t);
        }
        return ans;
    }
};

Go

func printVertically(s string) (ans []string) {
	words := strings.Split(s, " ")
	n := 0
	for _, w := range words {
		n = max(n, len(w))
	}
	for j := 0; j < n; j++ {
		t := []byte{}
		for _, w := range words {
			if j < len(w) {
				t = append(t, w[j])
			} else {
				t = append(t, ' ')
			}
		}
		for len(t) > 0 && t[len(t)-1] == ' ' {
			t = t[:len(t)-1]
		}
		ans = append(ans, string(t))
	}
	return
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

...