151. 反转字符串中的单词
题目描述
输入字符串 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 <= 10^4s只含英文大小写字母、数字和空格。s中至少有一个单词。
进阶：如果所用语言的字符串可以修改，能否只用 O(1) 额外空间就地完成？
解题思路：从后向前双指针
从右往左扫描，先遇到的就是原串最后一个单词。用 j 跳过空格找到单词的最后一个字符，再让 i 从 j 向左走到单词前面的空格（或 -1），s[i+1:j+1] 就是一个完整单词，追加到 words 末尾。然后令 j = i 继续找下一个单词。按这个顺序收集，words 天然就是反转后的顺序，最后用一个空格连接，多余空格自动被丢掉。
为什么正确
s[j+1:] 中的所有单词都已经按从右到左的顺序放进 words，且没有任何空格进入 words。
复杂度分析
时间 O(n)，每个字符被 i 或 j 经过一次；除结果外额外空间 O(n)（存放单词）。
易错点
直接用 s.split(" ") 会在连续空格处产生空字符串；从右往左取单词时，内层两个 while 都要先检查下标不越界（j >= 0、i >= 0）。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def reverseWords(self, s: str) -> str:
words = []
j = len(s) - 1
while j >= 0:
while j >= 0 and s[j] == ' ':
j -= 1
if j < 0:
break
i = j
while i >= 0 and s[i] != ' ':
i -= 1
words.append(s[i + 1:j + 1])
j = i
return ' '.join(words)class Solution {
public String reverseWords(String s) {
List<String> words = new ArrayList<>();
int j = s.length() - 1;
while (j >= 0) {
while (j >= 0 && s.charAt(j) == ' ') {
j--;
}
if (j < 0) {
break;
}
int i = j;
while (i >= 0 && s.charAt(i) != ' ') {
i--;
}
words.add(s.substring(i + 1, j + 1));
j = i;
}
return String.join(" ", words);
}
}class Solution {
public:
string reverseWords(string s) {
vector<string> words;
int j = (int)s.size() - 1;
while (j >= 0) {
while (j >= 0 && s[j] == ' ') {
j--;
}
if (j < 0) {
break;
}
int i = j;
while (i >= 0 && s[i] != ' ') {
i--;
}
words.push_back(s.substr(i + 1, j - i));
j = i;
}
string res;
for (int k = 0; k < (int)words.size(); k++) {
if (k) res += ' ';
res += words[k];
}
return res;
}
};func reverseWords(s string) string {
words := []string{}
j := len(s) - 1
for j >= 0 {
for j >= 0 && s[j] == ' ' {
j--
}
if j < 0 {
break
}
i := j
for i >= 0 && s[i] != ' ' {
i--
}
words = append(words, s[i+1:j+1])
j = i
}
return strings.Join(words, " ")
}var reverseWords = function(s) {
const words = [];
let j = s.length - 1;
while (j >= 0) {
while (j >= 0 && s[j] === ' ') {
j--;
}
if (j < 0) {
break;
}
let i = j;
while (i >= 0 && s[i] !== ' ') {
i--;
}
words.push(s.slice(i + 1, j + 1));
j = i;
}
return words.join(' ');
};function reverseWords(s: string): string {
const words: string[] = [];
let j = s.length - 1;
while (j >= 0) {
while (j >= 0 && s[j] === ' ') {
j--;
}
if (j < 0) {
break;
}
let i = j;
while (i >= 0 && s[i] !== ' ') {
i--;
}
words.push(s.slice(i + 1, j + 1));
j = i;
}
return words.join(' ');
}其他解法
分割后反转最短但依赖库函数；从后向前双指针手动提取单词，需要 O(n) 存放单词；整体反转再逐词反转可以原地完成。
解法 2：分割后反转 时间 O(n)，空间 O(n)
用语言自带的方法按空白分割字符串，自动丢弃多余空格。把得到的单词列表反转。用单个空格连接成结果。
代码只有一两行，实际开发首选。面试中通常不被接受，因为分割和连接都交给了库函数。
class Solution:
def reverseWords(self, s: str) -> str:
return ' '.join(reversed(s.split()))class Solution {
public String reverseWords(String s) {
List<String> words = new ArrayList<>(Arrays.asList(s.trim().split("\\s+")));
Collections.reverse(words);
return String.join(" ", words);
}
}class Solution {
public:
string reverseWords(string s) {
istringstream in(s);
vector<string> words;
string w;
while (in >> w) words.push_back(w);
reverse(words.begin(), words.end());
string res;
for (int k = 0; k < (int)words.size(); k++) {
if (k) res += ' ';
res += words[k];
}
return res;
}
};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, " ")
}var reverseWords = function(s) {
return s.trim().split(/\s+/).reverse().join(' ');
};function reverseWords(s: string): string {
return s.trim().split(/\s+/).reverse().join(' ');
}解法 3：整体反转再逐词反转 时间 O(n)，空间 O(1)
把字符串转成字符数组，先整体反转，单词顺序就反过来了，但每个单词内部也被倒置。再用写指针 idx 从左向右扫描：跳过空格，单词之间补一个空格，把单词字符搬到 idx 处，然后把这个单词反转回来。最后截取前 idx 个字符。
在字符数组可变的语言中额外空间为 O(1)，是进阶要求的做法。下标操作较多，要同时处理去多余空格和反转。字符串不可变的语言需要先复制成数组。
class Solution:
def reverseWords(self, s: str) -> str:
def rev(a, i, j):
while i < j:
a[i], a[j] = a[j], a[i]
i += 1
j -= 1
a = list(s)
n = len(a)
rev(a, 0, n - 1)
idx = 0
start = 0
while start < n:
if a[start] == ' ':
start += 1
continue
if idx > 0:
a[idx] = ' '
idx += 1
end = start
begin = idx
while end < n and a[end] != ' ':
a[idx] = a[end]
idx += 1
end += 1
rev(a, begin, idx - 1)
start = end
return ''.join(a[:idx])class Solution {
private void rev(char[] a, int i, int j) {
while (i < j) {
char t = a[i]; a[i] = a[j]; a[j] = t;
i++; j--;
}
}
public String reverseWords(String s) {
char[] a = s.toCharArray();
int n = a.length;
rev(a, 0, n - 1);
int idx = 0;
for (int start = 0; start < n; start++) {
if (a[start] == ' ') continue;
if (idx > 0) a[idx++] = ' ';
int end = start, begin = idx;
while (end < n && a[end] != ' ') a[idx++] = a[end++];
rev(a, begin, idx - 1);
start = end;
}
return new String(a, 0, idx);
}
}class Solution {
public:
string reverseWords(string s) {
int n = s.size();
reverse(s.begin(), s.end());
int idx = 0;
for (int start = 0; start < n; start++) {
if (s[start] == ' ') continue;
if (idx > 0) s[idx++] = ' ';
int end = start, begin = idx;
while (end < n && s[end] != ' ') s[idx++] = s[end++];
reverse(s.begin() + begin, s.begin() + idx);
start = end;
}
s.erase(s.begin() + idx, s.end());
return s;
}
};func reverseWords(s string) string {
rev := func(a []byte, i, j int) {
for i < j {
a[i], a[j] = a[j], a[i]
i++
j--
}
}
a := []byte(s)
n := len(a)
rev(a, 0, n-1)
idx := 0
for start := 0; start < n; start++ {
if a[start] == ' ' {
continue
}
if idx > 0 {
a[idx] = ' '
idx++
}
end, begin := start, idx
for end < n && a[end] != ' ' {
a[idx] = a[end]
idx++
end++
}
rev(a, begin, idx-1)
start = end
}
return string(a[:idx])
}var reverseWords = function(s) {
const rev = (a, i, j) => {
while (i < j) {
[a[i], a[j]] = [a[j], a[i]];
i++;
j--;
}
};
const a = s.split('');
const n = a.length;
rev(a, 0, n - 1);
let idx = 0;
for (let start = 0; start < n; start++) {
if (a[start] === ' ') continue;
if (idx > 0) a[idx++] = ' ';
let end = start;
const begin = idx;
while (end < n && a[end] !== ' ') a[idx++] = a[end++];
rev(a, begin, idx - 1);
start = end;
}
return a.slice(0, idx).join('');
};function reverseWords(s: string): string {
const rev = (a: string[], i: number, j: number): void => {
while (i < j) {
[a[i], a[j]] = [a[j], a[i]];
i++;
j--;
}
};
const a = s.split('');
const n = a.length;
rev(a, 0, n - 1);
let idx = 0;
for (let start = 0; start < n; start++) {
if (a[start] === ' ') continue;
if (idx > 0) a[idx++] = ' ';
let end = start;
const begin = idx;
while (end < n && a[end] !== ' ') a[idx++] = a[end++];
rev(a, begin, idx - 1);
start = end;
}
return a.slice(0, idx).join('');
}