LeetCode题练习与总结：反转字符串中的单词--151

一、题目描述

给你一个字符串 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 <= 10^4
• s 包含英文大小写字母、数字和空格 ' '
• s 中 至少存在一个 单词

二、解题思路

1. 首先，我们需要去除字符串s的前导空格和尾随空格，同时将字符串中间多余的空格缩减为一个空格。
2. 然后，我们将整个字符串反转。
3. 接下来，我们需要遍历反转后的字符串，将每个单词反转回原来的顺序。

三、具体代码

class Solution {public String reverseWords(String s) {// 去除前导和尾随空格，并将中间多余空格缩减为一个空格StringBuilder sb = trimSpaces(s);// 反转整个字符串reverse(sb, 0, sb.length() - 1);// 反转每个单词reverseEachWord(sb);return sb.toString();}private StringBuilder trimSpaces(String s) {int left = 0, right = s.length() - 1;// 去除前导空格while (left <= right && s.charAt(left) == ' ') left++;// 去除尾随空格while (left <= right && s.charAt(right) == ' ') right--;// 将中间多余空格缩减为一个空格StringBuilder sb = new StringBuilder();while (left <= right) {char c = s.charAt(left);if (c != ' ') {sb.append(c);} else if (sb.charAt(sb.length() - 1) != ' ') {sb.append(c);}left++;}return sb;}private void reverse(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 n = sb.length();int start = 0, end = 0;while (start < n) {// 循环至单词的末尾while (end < n && sb.charAt(end) != ' ') end++;// 翻转单词reverse(sb, start, end - 1);// 更新start，去找下一个单词end++;start = end;}}
}

四、时间复杂度和空间复杂度

1. 时间复杂度

• trimSpaces 方法：这个方法遍历了整个字符串一次，所以时间复杂度是 O(n)，其中 n 是字符串的长度。
• reverse 方法：这个方法是用来翻转字符串的一部分，它的时间复杂度是 O(m)，其中 m 是要翻转的部分的长度。
• reverseEachWord 方法：这个方法遍历了整个字符串一次，并且在每个单词上调用了一次 reverse 方法。假设单词的平均长度是 k，那么这个方法的时间复杂度是 O(n + k)，其中 n 是字符串的长度，k 是单词的平均长度。

综合起来，整个算法的时间复杂度是 O(n + k)，因为 trimSpaces 和 reverseEachWord 都是遍历整个字符串，而 reverse 是在单个单词上操作，所以单词的总长度是 n。

2. 空间复杂度

• trimSpaces 方法：这个方法创建了一个新的 StringBuilder 来存储处理后的字符串，所以空间复杂度是 O(n)，其中 n 是字符串的长度。
• reverse 方法和 reverseEachWord 方法：这两个方法都是原地操作，没有使用额外的空间，所以它们的空间复杂度是 O(1)。

综合起来，整个算法的空间复杂度是 O(n)，因为 trimSpaces 方法创建了一个新的 StringBuilder 来存储处理后的字符串。

五、总结知识点

1. 字符串处理：对字符串进行遍历、去除前后空格、缩减中间多余空格等操作。

2. StringBuilder 类的使用：StringBuilder 是一个可变的字符序列，用于高效地拼接字符串、修改字符串内容等。

3. 字符串反转：通过交换字符串首尾字符的位置，实现字符串的反转。

4. 循环和条件语句：使用 while 循环和 if 条件语句来控制程序的逻辑流程。

5. 字符数组与字符串的转换：StringBuilder 在内部维护一个字符数组，可以通过 append 方法添加字符，最终通过 toString 方法转换为字符串。

6. 边界条件处理：在去除前后空格和反转字符串时，需要考虑字符串为空或只有一个字符的边界情况。

7. 函数封装：将去除空格、反转字符串、反转每个单词等功能封装成单独的函数，提高代码的可读性和可维护性。

8. 指针或索引的使用：在遍历字符串时，使用指针或索引来跟踪当前处理的位置。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。