Version: Next

151.翻转字符串里的单词

151. 翻转字符串里的单词

难度 中等

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

说明：

  • 无空格字符构成一个 单词 。
  • 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
  • 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

示例 1：

输入："the sky is blue"
输出："blue is sky the"

示例 2：

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

示例 3：

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

示例 4：

输入：s = " Bob Loves Alice "
输出："Alice Loves Bob"

示例 5：

输入：s = "Alice does not even like bob"
输出："bob like even not does Alice"

提示：

  • 1 <= s.length <= 104
  • s 包含英文大小写字母、数字和空格 ' '
  • s 中 至少存在一个 单词

进阶：

  • 请尝试使用 O(1) 额外空间复杂度的原地解法。

消空格+整体翻转+单词翻转

消除字符串中的多余空格

步骤

  • 用 i 扫描 String，判断每一个字符是否为 空字符
  • cur 指针指向可以存放字符的位置
  • 如果 i 找到非空格字符
    • 将字符挪动到 cur 指向位置
    • i++, cur++
  • 如果 i 找到了 空格字符
    • 判断是不是从一个 非空格字符 而来，遇到的第一个 空格字符
      • 是：cur 位置也写入一个 空格字符，i++; cur++
      • 不是: i++，cur 不动
  • 完成遍历后
    • 如果原字符串不是以 空格 结尾，那么 cur 指向最后一个有效字符的下一个位置，在 数值上 = 字符串有效长度
    • 如果原字符串以 空格 、 多个空格 结尾：那么 cur 在最后一个有效字符后 多写了一个 空格 并且指向了 空格的下一个位置，数值上 = 字符串有效长度 + 1

image-20210411195546454

消除空格后翻转单词

步骤

  1. 将 [0, 字符串有效长度) 范围内的字符串 整体逆序
  2. 对每个单词进行逆序

image-20210411200137570

public String reverseWords(String s) {
if (s.length() == 1) return s;
char[] chars = s.toCharArray();
// 消除空格
boolean fromSpaceFlag = true;
// size 为字符串有效长度
int i = 0, cur = 0, size = 0;
while (i < chars.length) {
if (chars[i] != ' ') {
chars[cur++] = chars[i++];
fromSpaceFlag = false;
} else { // i 指向了一个 空格
if (!fromSpaceFlag) // 如果是从一个非空格字符来的
//
// cur 位置也写入一个空格
chars[cur++] = ' ';
i++;
fromSpaceFlag = true;
}
}
// 有效长度
size = fromSpaceFlag ? cur - 1 : cur;
// 整体逆序
reverseStr(chars, 0, size);
// 单词逆序
int left = 0, right = 1;
while (right < size) {
if (chars[right] != ' ') right++;
else {
reverseStr(chars, left, right);
right++;
left = right;
}
}
// 翻转最后一个单词
reverseStr(chars, left, size);
return new String(chars, 0, size);
}
private void reverseStr(char[] chars, int l, int r) {
r--;
while (l < r) {
char temp = chars[l];
chars[l] = chars[r];
chars[r] = temp;
l++;
r--;
}
}

消空格+按连续空格切分+集合逆序+拼接

  • 消除字符串两端的空格
  • 使用正则匹配 空格、连续空格，切分为字符串集合
  • 集合中的字符串之间逆序，字符串本身不逆序
  • 遍历 字符串集合 将各个字符串用 空格 拼接
String s = " the sky is blue ";
s = s.trim();
List<String> wordList = Arrays.asList(s.split("\\s+"));
Collections.reverse(wordList);
String reverse = String.join(" ", wordList);
System.out.println("reverse = " + reverse);