@(LeetCode)
问题描述
给定一个字符串 s。按单词出现的先后顺序，以纵向排列的方式返回，结果为一个字符串数组。每一个单词放在单独的一列，如果有需要加上空格，但是末尾不允许出现空格。
栗 1：
输入：s = "HOW ARE YOU"
输出：["HAY","ORO","WEU"]
解释：每个单词纵向排列如下。
"HAY"
"ORO"
"WEU"
栗 2：
输入：s = "TO BE OR NOT TO BE"
输出：["TBONTB","OEROOE"," T"]
解释：每个单词纵向排列如下，且末尾不能有空格。所以 T 后面无空格。
"TBONTB"
"OEROOE"
" T"
栗 3：
输入：s = "CONTEST IS COMING"
输出：["CIC","OSO","N M","T I","E N","S G","T"]
解释：每个单词纵向排列如下，同样 T 后面不能有空格。
"CIC"
"OSO"
"N M"
"T I"
"E N"
"S G"
"T"
注意：
-
1 <= s.length <= 200。 -
s只包含大写字母。 - 在两个单词之间只有一个空格。
解题思路
看过栗子后，题意应该比较清楚了。将每个单词纵向排列，必要时加空格，且末尾不能有空格。
- 纵向排列
纵向排列比较好办，类似组建二维数组的方式，只不过是纵向填充。
观察结果，我们可以发现单词中第一个字符对应第 1 行，第二个字符对应第 2 行，以此类推。因此，只需要遍历单词的字符，取到对应的行填入即可。
- 必要时加空格
若某个单词的长度 < 后面某个单词的长度，需要补加空格。如下所示：
HH 和 AM 后面有比其更长的单词。
s = "HH AM WHO"
"HAW"
"HMH"
" O"
- 末尾不能有空格
对于某个单词，其后没有比它更长的单词的时候，不需要加空格。
在下例中，当 AB 纵向排列时，其后不需要再加空格，因为它后面没有比它长的单词。
s = "HOW AB C"
"HAC"
"OB"
"W"
解法 1
我最初的想法是，补加空格是按照最长的单词去补，因此只需求出字符串中组最长的单词。在遍历每个单词的时候，计算出需要补的空格数进行填补即可。但是，会产生末尾空格的情况，用 trim 方式再次进行处理。
这种方式虽然能达到效果，但肯定不太好。需要遍历多次，外加额外的去除空格处理。
代码如下：
var printVertically = function(s) {
let i = 0
let maxLen = 0
let len = 0
// 计算单词的最大长度
while (i <= s.length) {
if (i === s.length || s[i] === ' ') {
if (len > maxLen) {
maxLen = len
}
len = 0
} else {
len += 1
}
i += 1
}
// 初始化结果数组
let result = new Array()
let j = 0
while (j < maxLen) {
result.push('')
j += 1
}
let k = 0
let index = -1
while (k <= s.length) {
// 到末尾或者一个单词结束
if (k === s.length || s[k] === ' ') {
// 当前单词长度
let m = index + 1
// 如果比最大单词长度短，则补空格
while (m < maxLen) {
let list = result[m]
list += ' '
result[m] = list
m += 1
}
index = -1
} else {
// 行数
index += 1
// 取出对应的行
let list = result[index]
list += s[k]
result[index] = list
}
k += 1
}
// 去除末尾空格
const trimmedResult = result.map(str => {
return str.trimEnd()
})
return trimmedResult
};
解法 2
我们再来回顾一下什么情况下该加空格？
若某个单词的长度 < 后面某个单词的长度，需要加空格。
所以主要问题在于，如何知道某个单词后面是否有单词比它长？
稍微想一想，如果从头开始遍历，是无法得知的。但是，换种思路，倒着遍历，却是可以的。
因此，我们只需要记录从后往前遍历时最大单词的长度 maxLen，然后与当前单词长度 curLen 比较。如果 curLen < maxLen，则需加空格，反之不需要。
这样一次遍历就可以解决问题，也不会有末尾空格的困扰。因为只在该加的地方才加了空格。
注意：由于是反向遍历，在取单词时，需要注意字符串相加的顺序。
// 反向遍历, 97.77%
var printVertically2 = function(s) {
let result = new Array()
// 单词
let word = ''
// 是否是完整单词
let wordFlag = false
// 记录已遍历单词最大长度
let preLen = 0
// 从末尾遍历
let i = s.length - 1
while (i >= 0) {
if (s[i] !== ' ') {
// 注意顺序
word = s[i] + word
// 一个完整单词
if (i === 0) {
wordFlag = true
}
} else {
// 一个完整的单词
wordFlag = true
}
if (wordFlag) {
// 遍历单词
let j = 0
while (j < word.length) {
let list = ''
// 取数组元素，不存在
if (result.length <= j) {
result.push(list)
} else {
list = result[j]
}
// 注意顺序
list = word[j] + list
result[j] = list
j += 1
}
// 如果字符串长度小于前面最大字符串长度，需要填补空格
if (word.length < preLen) {
let k = 0
while (k < preLen - word.length) {
const m = k + word.length
let list = ''
// 不存在
if (result.length <= m) {
result.push(list)
} else {
list = result[m]
}
// 注意顺序
list = ' ' + list
result[m] = list
k += 1
}
}
// 更新最大长度
if (word.length > preLen) {
preLen = word.length
}
wordFlag = false
word = ''
}
i -= 1
}
return result
}
解法 3
思路
以上两种解法都是以一个单词纵向排列的切入点去思考，即按列生成。其实我们也可以考虑按行生成。
通过观察，我们可以发现如下规律：
- 第一行：第一个单词的第一个字符 + 第二个单词的第一个字符 + ... + 第
m个单词的第一个字符 - 第二行：第一个单词的第二个字符 + 第二个单词的第二个字符 + ... + 第
m个单词的第一个字符 - ...
- 第 n 行：第一个单词的第
n个字符（如果没有，则为空格） + 第二个单词的第n个字符 + ... + 第m个单词的第一个字符
但这样会产生末尾空格的问题，不过也好解决。只需取子串 [0, index]，其中 index 为长度 >= n 的最后一个单词的索引，即是第几个单词。
栗子
比如 s = "WHAT DO YOU DO"，下面列出排列过程。
- 第一行，分别取每个单词的第一个字符。
"WAYD" - 第二行，分别取每个单词的第二个字符。
"HOOO" - 第三行，初始结果为
"A U "。由于DO/DO的长度小于3，所以补空格。但这样U后面会出现末尾空格，而长度>= 3的单词索引为2，那么取其子串[0,2]，结果为"A U"。 - 第四行，初始结果为
"T "。由于ARE/YOU/DO的长度均小于4，所以补空格。同样的出现了末尾空格，而长度>= 4的单词索引为0，所以取其子串[0, 0]，结果为"T"。
因此，最终结果为：
"WDYD"
"HOOO"
"A U"
"T"
代码如下：
// 横向填充, 58.36%
var printVertically3 = function(s) {
if (s && s.length > 0) {
// 分隔单词
const wordList = s.split(' ')
if (wordList && wordList.length > 0) {
let index = 0
let maxLen = 1
let result = new Array()
// 逐步生成行，最大行数为单词的最大长度
while (index < maxLen) {
let str = ""
let i = 0
let lastIndex = 0
while (i < wordList.length) {
const word = wordList[i]
// 同时计算最大长度
if (word.length > maxLen) {
maxLen = word.length
}
if (index < word.length) {
// 记录单词索引
lastIndex = i
str += word[index]
} else {
// 补空格
str += " "
}
i += 1
}
index += 1
// 取子串
const substr = str.slice(0, lastIndex + 1)
result.push(substr)
}
return result
}
}
return []
}
网友评论