反转字符串里的单词:倒词序,不倒字母
先切出单词再倒着拼,空格会被 Fields 吃掉。要原地就先整串反转,再对每个单词反转一次:词序已经反了,字母序被第二次反转正回来。
目标是单词顺序颠倒、单词内部字母顺序不变,且首尾无空格、词间一个空格。切词:Fields 拆出单词,数组双指针对调,Join 回去。原地:先反转整个字符数组,再对每个单词区间反转。时间 O(n)。切词额外 O(n) 空间。
给你字符串 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 或自己扫的时候跳过连续空格,才能保证词间恰好一个空格。
整串先反,每个单词再反
切词要额外数组。若必须原地,缺口变成:怎样在字符数组上既倒词序、又保持每个词内部。先把整串反转。主例变成 "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"。若输入带多余空格,整串反转之前先把空格压缩成词间一个、去掉首尾,否则第二次按空格切词会把空段当成单词。
Go:拆词逆序
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 会留下空串。
- 两次反转可原地。第二次只翻每个单词的区间。