当前:LC151 · 反转字符串中的单词 · 首次出现于 Day 15 · 路径:顶栏「56天打卡」→ 点击 LC 题号 → 逐题动画

LC151 · Reverse Words in a String · 字符串

反转字符串里的单词:倒词序,不倒字母

先切出单词再倒着拼,空格会被 Fields 吃掉。要原地就先整串反转,再对每个单词反转一次:词序已经反了,字母序被第二次反转正回来。

目标是单词顺序颠倒、单词内部字母顺序不变,且首尾无空格、词间一个空格。切词:Fields 拆出单词,数组双指针对调,Join 回去。原地:先反转整个字符数组,再对每个单词区间反转。时间 O(n)。切词额外 O(n) 空间。

时间 O(n)空间 O(n)(split)结论先行 · 全文约 6 节
导读

给你字符串 s,反转其中单词的顺序。单词是连续非空格字符。返回值里单词之间只留一个空格,首尾不能有空格。输入可能有前导、尾随、词间多个空格。

主例 "the sky is blue" → "blue is sky the"。the 仍是 t-h-e,只是四个词的排列倒过来。" hello world " 要收成 "world hello"。

整串反转一次会得到 "eulb si yks eht",词序对了,字母全反了。本文要回答:切词怎么去多余空格,以及为什么再反一次每个单词就能同时修好词序和字序。

切出单词,倒数组,再拼回一个空格

题目要的是词的排列,不是字符的排列。最直接的缺口补法:先把词拿出来,变成一个数组,再把数组倒过来。按空白切的时候,连续空格会产生空串,必须丢掉,否则 Join 会在词之间留下双空格,首尾也会脏。

Go 的 strings.Fields 按任意空白切,并且丢掉空段,主例直接得到 [the, sky, is, blue]。双指针 i、j 对调数组两端,得到 [blue, is, sky, the]。再用单个空格 Join。时间和输入长度线性,额外开一个词数组。

用手走主例。切完四个词。先写出最后一个 blue,再接 is,再接 sky,最后接 the。演示四帧从下标 3 走到 0,拼出 "blue is sky the"。输入全是空格时 Fields 得到空切片,Join 得到空串,符合「没有单词」。

空格是分隔符不是单词按单个空格 Split 会留下空串。Fields 或自己扫的时候跳过连续空格,才能保证词间恰好一个空格。
拆出单词,逆序拼回
the·sky·is·blue
theskyisblue
blue

整串先反,每个单词再反

切词要额外数组。若必须原地,缺口变成:怎样在字符数组上既倒词序、又保持每个词内部。先把整串反转。主例变成 "eulb si yks eht"。单词的排列已经是 blue、is、sky、the 的倒字母版——词序对了,每个词内部反了。

再对每个单词做一次区间反转。eulb 反成 blue,si 反成 is,yks 反成 sky,eht 反成 the。两次反转抵消的是字母序,留下的是词序。这和「矩阵转置再翻」同类:全局变换一次,再在局部把不该动的改回去。

用手走这一半。演示从已经整串反转后的 "eulb si yks eht" 起步。先把第一个词 eulb 正成 blue,串变成 "blue si yks eht"。再正 si、yks、eht,得到 "blue is sky the"。若输入带多余空格,整串反转之前先把空格压缩成词间一个、去掉首尾,否则第二次按空格切词会把空段当成单词。

整串反转后逐词再反转
eulb·si·yks·eht
eulbsiykseht
第一次反转后:单词顺序已反

Go:拆词逆序

solution.goGo
import "strings"
func reverseWords(s string) string {
words := strings.Fields(s)
for i, j := 0, len(words)-1; i < j; i, j = i+1, j-1 {
words[i], words[j] = words[j], words[i]
}
return strings.Join(words, " ")
}

1Fields 按空白切并丢掉空段,主例得到四个词,首尾空格一起消失。

2对调的是词,不是字母。the 仍是 the。

3Join 用单个空格。空输入得到空串。

总结

切词倒序拼接,或整串反再逐词反。主例都得到 blue is sky the。

  • 反的是词序。整串只反一次会得到 eulb si yks eht,字母是反的。
  • Fields 负责多余空格。按单个空格 Split 会留下空串。
  • 两次反转可原地。第二次只翻每个单词的区间。
同族题目
LC186反转字符串中的单词 II(两次反转)LC344反转字符串LC14最长公共前缀