https://leetcode.cn/problems/reverse-words-in-a-string/

题面

给定一个字符串，逐个翻转字符串中的每个单词。

示例 1：
输入: “the sky is blue”
输出: “blue is sky the”

示例 2：
输入: “ hello world! “
输出: “world! hello”
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：
输入: “a good example”
输出: “example good a”
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

思路 时间O(n)，空间O(1)或O(n)

用split这题就太简单，所以要求不要使用辅助空间，空间复杂度为O(1)。

解题思路如下：

  • 移除多余空格
  • 将整个字符串反转
  • 将每个单词反转

解法①

不使用Java内置方法。

  1. 去除首尾以及中间多余空格
  2. 反转整个字符串
  3. 反转各个单词
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public String reverseWords(String s) {
    // 1. 去除首尾以及中间多余空格
    StringBuilder sb = removeSpace(s);
    // 2. 反转整个字符串
    reverseString(sb, 0, sb.length() - 1);
    // 3. 反转各个单词
    reverseEachWord(sb);
    return sb.toString();
}

private StringBuilder removeSpace(String s) {
    StringBuilder sb = new StringBuilder();
    int start = 0;
    int end = s.length() - 1;
    while (s.charAt(start) == ' ') start++;
    while (s.charAt(end) == ' ') end--;
    while (start <= end) {
        char c = s.charAt(start);
        if (c != ' ' || sb.charAt(sb.length() - 1) != ' ')
            sb.append(c);
        start++;
    }
    return sb;
}

// 反转字符串指定区间 [start, end] 的字符
public void reverseString(StringBuilder sb, int start, int end) {
    while (start < end) {
        char temp = sb.charAt(start);
        sb.setCharAt(start, sb.charAt(end));
        sb.setCharAt(end, temp);
        start++;
        end--;
    }
}

private void reverseEachWord(StringBuilder sb) {
    int start = 0;
    int end = 1;
    int n = sb.length();
    while (start < n) {
        while (end < n && sb.charAt(end) != ' ')
            end++;
        reverseString(sb, start, end - 1);
        start = end + 1;
        end = start + 1;
    }
}

解法②

（待补充）

解法③

（待补充）

解法④

（待补充）