反转字符串中的单词
给你一个字符串 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
中 至少存在一个 单词
**进阶:**如果字符串在你使用的编程语言中是一种可变数据类型,请尝试使用 O(1)
额外空间复杂度的 原地 解法。
方法一:
遍历数组然后遇见空格就将前一个单词加入结果集,如果有多个空格其余空格就跳过。
func reverseWords(s string) string {
s = strings.Trim(s, " ")
l := 0
res := ""
for i, i2 := range s {
if i2 == ' ' {
if i == l {
l = i + 1
continue
}
res = " " + s[l:i] + res
l = i + 1
}
}
res = s[l:] + res
return res
}
时间复杂度O(n),空间复杂度O(n)
因为Go语言string不能更改的特性,所以不存在原地修改。
方法二:
解题思路:代码随想录
func reverseWords(s string) string {
// 删除前后多余空格
s = strings.Trim(s, " ")
// 清除中间多余空格
bs := []byte(s)
l, f := 0, 0
num := 0
for f < len(bs) {
if bs[f] == ' ' {
f++
num++
if num == 1 {
bs[l] = ' '
l++
}
} else {
bs[l] = bs[f]
l++
f++
if num != 0 {
num = 0
}
}
}
bs = bs[:l]
fmt.Println(string(bs))
// 反转整个字符串
reverse(bs)
// 反转每个单词
lift, right := 0, 0
for right < len(bs) {
if bs[right] == ' ' {
reverse(bs[lift:right])
lift = right + 1
}
right++
}
reverse(bs[lift:right])
return string(bs)
}
func reverse(bs []byte) {
l := 0
r := len(bs) - 1
for l < r {
bs[l], bs[r] = bs[r], bs[l]
l++
r--
}
}
时间复杂度O(n),虽然在for循环里进行了次反转操作,但以为单词长度一般不会过长,可视为常数,空间复杂度O(n)