21.反转字符串中的单词
题目
给你一个字符串 s ，请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
示例 1:
- 输入：s = "the sky is blue"
- 输出："blue is sky the"
示例 2:
- 输入：s = " hello world "
- 输出："world hello"
- 解释：反转后的字符串中不能存在前导空格和尾随空格。
示例 3:
- 输入：s = "a good example"
- 输出："example good a"
- 解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。
提示:
- 1 <= s.length <= 104
- s 包含英文大小写字母、数字和空格 ' '
- s 中 至少存在一个 单词
思路
- 倒序遍历，记录每个单词的起始和结束长度
- 结果中累加每个单词，注意在加下一个单词的时候需要提前加上空格
- 遍历到最后一个空格或者第一个元素截止
- 注意如果是第一个元素截止的时候需要考虑第一个元素是不是空格" "，例如: " asdasd df f"
- 如果是空格，需要从i + 1开始
- 如果不是空格，需要从0开始
class Solution:
def reverseWords(self, s: str) -> str:
length = len(s)
result = ""
last = -1
for i in reversed(range(length)):
if last == -1 and s[i] != " ":
last = i
if last > -1 and (s[i] == " " or i == 0):
if result != "":
result += " "
if i == 0 and s[i] != " ":
result += s[0: last + 1]
else:
result += s[i + 1: last + 1]
last = -1
return result
class Solution {
fun reverseWords(s: String): String {
return s.trim().split(" ").filter {
it.isNotEmpty()
}.reversed().joinToString(" ")
}
}
双指针方式:
class Solution {
fun reverseWords(s: String): String {
val sb = StringBuilder()
var lastIndex = s.length - 1
while (lastIndex >= 0) {
if(s[lastIndex] != ' ') {
// 最后一个非空格的字符
var wordFirstIndex = lastIndex
while (wordFirstIndex >= 0 && s[wordFirstIndex] != ' ') {
// 继续往前找最后一个单词
wordFirstIndex --
}
if (sb.isNotEmpty()) {
// 前面有单词了，加空格
sb.append(' ')
}
// string.subString()会创建新的 String 对象，换成 sb.append(s, start, end) 直接从原字符串追加：
sb.append(s, wordFirstIndex + 1, lastIndex + 1)
// 最后一个单词弄完了，移动lastIndex继续循环
lastIndex = wordFirstIndex
} else {
// 最后一个是空格，迁移lastIndex指针
lastIndex--
}
}
return sb.toString()
}
}
复杂度分析:
- 时间复杂度 O(N) ： 其中 N 为字符串 s 的长度，线性遍历字符串。
-
空间复杂度 O(N) ： 新建的 list(Python) 或 StringBuilder(Java) 中的字符串总长度 ≤N ，占用 O(N) 大小的额外空间。
- 邮箱 ：charon.chui@gmail.com
- Good Luck!