给你一个字符串 s ，请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。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 <= 104
- s 包含英文大小写字母、数字和空格 ' '
- s 中 至少存在一个 单词
思路
这道题初看题目觉得非常简单, 但实际写起来有很多需要考虑的地方. 有两种解法, 分别是自定义方法和使用队列(还可以使用语言自带的方法, 这里不演示了).
解题的思路比较简单, 比较难的是代码实现中要考虑的内容, 所以代码中的注释比较多
自定义方法
由于步骤比较多, 所以建议分多个方法来实现. 首先去除字符串中的空格, 确保每个单词之间只有一个空格, 而字符串两端没有空格.
接下来将整个字符串反转, 然后再将每个单词反转即可.
队列
首先去除两侧字符, 建立一个队列和一个StringBuilder, 使用循环将单词添加到StringBuilder中, 若检测到空格则将StringBuilder中的内容push到队列里. 在循环结束后将StringBuilder中剩余的内容push到队列里. 最后返回时添加空格即可.
代码实现
自定义方法:
public class Solution {
public static String reverseWords(String s) {
// 去除空格
StringBuilder sb = removeSpace(s);
// 反转字符串
reverse(sb, 0, sb.length() - 1);
// 反转单词
reverseWord(sb);
return sb.toString();
}
private static void reverseWord(StringBuilder sb) {
int length = sb.length();
int start = 0, end = 0;
while (start < length) {
// 检测单词的末尾, 若检测到空格则说明当前单词已经结束
while (end < length && sb.charAt(end) != ' ') {
end++;
}
reverse(sb, start, end - 1); // 因为end在空格位置上, 所以传入end - 1
start = end + 1; // 因为end在空格位置上, 所以下一个单词的开始应该为end + 1
end++;
}
}
private static void reverse(StringBuilder sb, int left, int right) {
// 交换两侧字符位置
while (left < right) {
char temp = sb.charAt(left);
sb.setCharAt(left++, sb.charAt(right));
sb.setCharAt(right--, temp);
}
}
private static StringBuilder removeSpace(String s) {
int left = 0, right = s.length() - 1;
// 去除开头的空格
while (left <= right && s.charAt(left) == ' ') {
++left;
}
// 去除末尾的空格
while (left <= right && s.charAt(right) == ' ') {
--right;
}
StringBuilder stringBuilder = new StringBuilder();
// 去除单词之间的空格
while (left <= right) {
char c = s.charAt(left);
if (c != ' ') { // 若不为空格则将字符添加到stringBuilder
stringBuilder.append(c);
} else if(stringBuilder.charAt(stringBuilder.length() - 1) != ' ') { // 若StringBuilder的最后一位不是空格则表示当前单词还没有空格分隔, 所以添加一个空格
stringBuilder.append(c);
}
++left;
}
return stringBuilder;
}
}
队列:
public class Solution {
public String reverseWords(String s) {
int left = 0, right = s.length() - 1;
// 去除左侧空格
while (left <= right && s.charAt(left) == ' ') {
left++;
}
// 去除右侧空格
while (left < right && s.charAt(right) == ' ') {
right--;
}
Deque<String> deque = new ArrayDeque<>();
StringBuilder sb = new StringBuilder();
while (left <= right) {
char c = s.charAt(left);
if ((sb.length() != 0) && (c == ' ')) { // 若StringBuilder中有字符, 且当前字符为空格
deque.offerFirst(sb.toString()); // 将StringBuilder中的内容添加到队列中
sb.setLength(0); // 将StringBuilder中的内容清空
} else if (c != ' ') {
sb.append(c); // 添加字符
}
left++;
}
deque.offerFirst(sb.toString()); // 将StringBuilder中剩余的内容添加到队列
return String.join(" ", deque); // 从队列中取出单词, 并在它们直接使用空格分隔
}
}