反转字符串中的单词 III 图解题解

这道题到底在问什么

输入

s = "Let's take LeetCode contest"

输出

"s'teL ekat edoCteeL tsetnoc"

最优解：一步一步想明白

1. 3记住这句口诀：每个单词左右各放一个指针，往中间夹着两两交换，空格不动、顺序不变。下面每帧都在套它。
2. 4先把句子摊成一排字符格子。灰色的两格是空格，它们把句子切成三个单词 Let、us、code。空格永远不动，我们只在每个单词内部做交换。
3. 5扫到第 1 个单词的开头，左指针 l 落在下标 0，也就是字符 「L」。接着要找这个单词的右端在哪。
4. 6右指针 r 一路向右滑，碰到空格或句尾就停，停在下标 2（字符 「t」）。这样单词 「Let」 的左右两端 l=0、r=2 都框定了。
5. 7现在 l=0 在 r=2 的左边，符合「l 在 r 左边就交换」的条件。把这两格的字母 「L」 和 「t」 对调一下。
6. 8交换好了，下标 0 变成 「t」，下标 2 变成 「L」。然后 l 向右走一步、r 向左走一步，继续往中间夹。
7. 9两个指针碰头了，停在同一格 1。中间这个字符 「e」 跟自己交换没意义，所以单词长度是奇数时，正中间那一格保持不动。
8. 10这个单词反转完成，标成绿色，结果是 「teL」。注意它还在原来的位置上，空格也没挪，整句的单词顺序丝毫没变。
9. 11扫到第 2 个单词的开头，左指针 l 落在下标 4，也就是字符 「u」。接着要找这个单词的右端在哪。
10. 12右指针 r 一路向右滑，碰到空格或句尾就停，停在下标 5（字符 「s」）。这样单词 「us」 的左右两端 l=4、r=5 都框定了。
11. 13现在 l=4 在 r=5 的左边，符合「l 在 r 左边就交换」的条件。把这两格的字母 「u」 和 「s」 对调一下。
12. 14交换好了，下标 4 变成 「s」，下标 5 变成 「u」。然后 l 向右走一步、r 向左走一步，继续往中间夹。
13. 15l 已经走到 r 的右边，「l 在 r 左边」这个条件不成立了，交换就此打住。单词长度是偶数时，正好两两配对、没有落单的字符。
14. 16这个单词反转完成，标成绿色，结果是 「su」。注意它还在原来的位置上，空格也没挪，整句的单词顺序丝毫没变。
15. 17扫到第 3 个单词的开头，左指针 l 落在下标 7，也就是字符 「c」。接着要找这个单词的右端在哪。
16. 18右指针 r 一路向右滑，碰到空格或句尾就停，停在下标 10（字符 「e」）。这样单词 「code」 的左右两端 l=7、r=10 都框定了。
17. 19现在 l=7 在 r=10 的左边，符合「l 在 r 左边就交换」的条件。把这两格的字母 「c」 和 「e」 对调一下。
18. 20交换好了，下标 7 变成 「e」，下标 10 变成 「c」。然后 l 向右走一步、r 向左走一步，继续往中间夹。
19. 21现在 l=8 在 r=9 的左边，符合「l 在 r 左边就交换」的条件。把这两格的字母 「o」 和 「d」 对调一下。
20. 22交换好了，下标 8 变成 「d」，下标 9 变成 「o」。然后 l 向右走一步、r 向左走一步，继续往中间夹。
21. 23l 已经走到 r 的右边，「l 在 r 左边」这个条件不成立了，交换就此打住。单词长度是偶数时，正好两两配对、没有落单的字符。
22. 24这个单词反转完成，标成绿色，结果是 「edoc」。注意它还在原来的位置上，空格也没挪，整句的单词顺序丝毫没变。
23. 25三个单词全部反转好了，拼起来正是 teL su edoc。每个单词内部倒过来，空格和单词的先后顺序原样保留，和一开始算出的目标一模一样。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def reverseWords(self, s: str) -> str:
        return " ".join(t[::-1] for t in s.split())

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    string reverseWords(string s) {
        stringstream ss(s);
        string t;
        string ans;
        while (ss >> t) {
            reverse(t.begin(), t.end());
            ans += t;
            ans.push_back(' ');
        }
        ans.pop_back();
        return ans;
    }
};

import java.util.*;
class Solution {
    public String reverseWords(String s) {
        String[] words = s.split(" ");
        for (int i = 0; i < words.length; ++i) {
            words[i] = new StringBuilder(words[i]).reverse().toString();
        }
        return String.join(" ", words);
    }
}

复杂度

面试官可能追问