题目描述
给定一个字符串 s，反转字符串中每个单词的字符顺序，同时保留空格和单词的初始顺序。
示例 1:
输入: s = "Let's code in Python" 输出: "s'teL edoc ni nohtyP"
示例 2:
输入: s = "a good example" 输出: "a doog elpmaxe"
思路及实现
方式一：使用双指针反转字符串
思路
- 首先将字符串按空格分割成单词数组。
- 遍历单词数组，对每个单词使用双指针进行反转。
- 将反转后的单词重新拼接成字符串。
代码实现
Java版本
public class Solution { public String reverseWords(String s) { // 先将字符串按空格分割成单词数组 String[] words = s.split("\\s+"); // 反转单词数组 reverse(words, 0, words.length - 1); // 使用StringBuilder将单词数组重新组合成字符串 StringBuilder sb = new StringBuilder(); for (String word : words) { sb.append(word).append(" "); } // 移除末尾多余的空格并返回结果 return sb.toString().trim(); } // 反转数组指定区间的元素 private void reverse(String[] arr, int start, int end) { while (start < end) { String temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; start++; end--; } } /** public static void main(String[] args) { Solution solution = new Solution(); String s = "the sky is blue"; String reversed = solution.reverseWords(s); System.out.println(reversed); // 输出: "blue is sky the" } */ }
说明：
Java中使用
StringBuilder的reverse方法反转字符串，然后遍历单词数组，将反转后的单词依次添加到StringBuilder中，最后返回去除末尾空格的字符串。
C语言版本
#include <stdio.h> #include <string.h> #include <stdlib.h> void reverse(char *start, char *end) { char temp; while (start < end) { temp = *start; *start++ = *end; *end-- = temp; } } char *reverseWords(char *s) { char *word_start = NULL; char *temp = s; int len = strlen(s); for (int i = 0; i <= len; i++) { if (s[i] == ' ' || s[i] == '\0') { if (word_start) { reverse(word_start, temp - 1); word_start = NULL; } } else if (!word_start) { word_start = &s[i]; } if (s[i] == '\0') { if (word_start) { reverse(word_start, temp - 1); } } } return s; }
说明：
C语言中没有直接反转字符串的函数，所以需要自己实现
reverse函数。通过遍历字符串，找到每个单词的起始和结束位置，然后调用reverse函数反转单词。
Python3版本
def reverseWords(s: str) -> str: words = s.split() reversed_words = [word[::-1] for word in words] return ' '.join(reversed_words)
说明：
Python3中利用列表推导式和字符串切片
[::-1]来反转每个单词，然后使用join方法将反转后的单词拼接成字符串。
Golang版本
package main import ( "fmt" "strings" ) func reverseWords(s string) string { words := strings.Fields(s) reversedWords := make([]string, len(words)) for i, word := range words { runes := []rune(word) for j, k := 0, len(runes)-1; j < k; j, k = j+1, k-1 { runes[j], runes[k] = runes[k], runes[j] } reversedWords[i] = string(runes) } return strings.Join(reversedWords, " ") } func main() { s := "Let's code in Python" fmt.Println(reverseWords(s)) }
说明：
Golang中同样使用
strings.Fields分割字符串，然后遍历单词数组，对每个单词使用双指针反转字符顺序，最后使用strings.Join拼接反转后的单词。
复杂度分析
复杂度分析
时间复杂度：O(n)
- Java: O(n)，其中 n 是字符串 s 的长度。这是因为我们需要遍历整个字符串来分割单词，并且对于每个单词，反转操作也是线性的。
- C: O(n)，原因与 Java 类似，需要遍历整个字符串进行单词分割和反转。
- Python3: O(n)，Python 的字符串操作也是线性的。
- Golang: O(n)，同样是线性的时间复杂度，因为需要遍历字符串和反转每个单词。
空间复杂度: O(n)/O(1)
- Java: O(n)，
StringBuilder和 单词数组都需要额外的空间来存储结果。 - C: O(1)，除了输入字符串本身占用的空间外，没有使用额外的动态分配空间。这里假设反转操作是在原字符串上进行的。
- Python3: O(n)，列表推导式和字符串连接都会使用额外的空间。
- Golang: O(n)，
reversedWords切片需要额外的空间来存储反转后的单词。
方式二：递归
思路
使用递归来实现字符串中单词的反转，我们可以将问题分解为两个子问题：
- 反转字符串中的最后一个单词。
- 递归地反转除最后一个单词之外的其他部分，并将反转后的结果与第1步中反转的最后一个单词连接起来。
具体步骤如下：
- 找到最后一个单词的起始位置：我们可以从字符串的末尾开始遍历，找到最后一个单词的起始位置。这通常是通过找到最后一个非空格字符的位置，然后向前遍历直到遇到空格或字符串的起始位置。
- 反转最后一个单词：使用双指针法，一个指针指向单词的起始位置，另一个指针指向单词的末尾位置，然后交换两个指针所指向的字符，直到两个指针相遇或交错。
- 递归处理剩余部分：将最后一个单词之后的所有字符（包括空格）作为新的字符串，递归调用反转函数。
- 拼接结果：将递归返回的结果与第2步中反转的最后一个单词拼接起来，得到最终的结果。
代码实现
Java版本
public class ReverseWordsRecursively { public String reverseWords(String s) { // 处理边界情况 if (s == null || s.isEmpty()) { return s; } // 去除字符串两端的空格 s = s.trim(); // 递归反转字符串中的单词 return reverseWordsRecursiveHelper(s, s.length() - 1); } private String reverseWordsRecursiveHelper(String s, int endIndex) { if (endIndex < 0) { return ""; } // 找到最后一个单词的起始位置 int startIndex = endIndex; while (startIndex >= 0 && s.charAt(startIndex) != ' ') { startIndex--; } // 反转最后一个单词 StringBuilder reversedWord = new StringBuilder(); for (int i = startIndex + 1; i <= endIndex; i++) { reversedWord.append(s.charAt(i)); } // 递归处理剩余部分，并与反转的单词拼接 String remaining = reverseWordsRecursiveHelper(s, startIndex - 1); return (remaining.isEmpty() ? "" : remaining + " ") + reversedWord.toString(); } public static void main(String[] args) { ReverseWordsRecursively solution = new ReverseWordsRecursively(); String s = "Let's code together"; String reversed = solution.reverseWords(s); System.out.println(reversed); // 输出 "s'teL edoc rehtegot" } }
C语言版本
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdbool.h> void reverseRange(char *start, char *end) { char temp; while (start < end) { temp = *start; *start++ = *end; *end-- = temp; } } char *reverseWordsRecursive(char *s, int endIndex) { if (endIndex < 0) { return strdup(""); } // 找到最后一个单词的起始位置 int startIndex = endIndex; while (startIndex >= 0 && s[startIndex] != ' ') { startIndex--; } // 反转最后一个单词 reverseRange(&s[startIndex + 1], &s[endIndex]); // 递归处理剩余部分 char *remaining = reverseWordsRecursive(s, startIndex - 1); // 拼接结果 int remainingLength = strlen(remaining); int newLength = endIndex - startIndex + 1 + remainingLength; char *result = (char *)malloc(newLength + 1); // +1 for null terminator if (remainingLength > 0) { strcpy(result, remaining); strcat(result, " "); } strcat(result, &s[startIndex + 1]); // 拼接反转后的最后一个单词 result[newLength] = '\0'; // 添加字符串结束符 // 释放递归调用中分配的内存 free(remaining); return result; } char *reverseWords(char *s) { // 去除字符串两端的空格 int length = strlen(s); int start = 0; while (start < length && s[start] == ' ') { start++; } int end = length - 1; while (end >= start && s[end] == ' ') { end--; } // 复制处理后的字符串到新数组（可选，取决于原字符串是否可修改） char *processed = (char *)malloc(end - start + 2); // +2 for possible spaces and null terminator strncpy(processed, s + start, end - start + 1); processed[end - start + 1] = '\0'; // 递归反转单词 char *reversed = reverseWordsRecursive(processed, end - start); // 释放处理后的字符串内存 free(processed); return reversed; } int main() { char s[] = "Let's code together "; char *reversed = reverseWords(s); printf("%s\n", reversed); // 输出 "s'teL edoc rehtegot" // 释放最终结果的内存 free(reversed); return 0; }
Python3
def reverse_range(s, start, end): return s[:start] + s[start:end][::-1] + s[end:] def reverse_words_recursive(s, end_index): if end_index < 0: return "" # 找到最后一个单词的起始位置 start_index = end_index while start_index >= 0 and s[start_index] != ' ': start_index -= 1 # 反转最后一个单词 reversed_word = s[start_index + 1:end_index + 1][::-1] # 递归处理剩余部分，并与反转的单词拼接 remaining = reverse_words_recursive(s, start_index - 1) return (remaining + " " if remaining else "") + reversed_word def reverse_words(s): # 去除字符串两端的空格 s = s.strip() # 递归反转单词 reversed_s = reverse_words_recursive(s, len(s) - 1) return reversed_s # 测试 s = "Let's code together" reversed_s = reverse_words(s) print(reversed_s) # 输出 "s'teL edoc rehtegot"
Golang版本
package main import ( "fmt" "strings" ) func reverseRange(s string, start, end int) string { runes := []rune(s) for i, j := start, end; i < j; i, j = i+1, j-1 { runes[i], runes[j] = runes[j], runes[i] } return string(runes) } func reverseWordsRecursive(s string, endIndex int) string { if endIndex < 0 { return "" } // 找到最后一个单词的起始位置 startIndex := endIndex for startIndex >= 0 && s[startIndex] != ' ' { startIndex-- } // 反转最后一个单词 reversedWord := reverseRange(s, startIndex+1, endIndex) // 递归处理剩余部分，并与反转的单词拼接 remaining := reverseWordsRecursive(s, startIndex-1) return remaining + " " + reversedWord } func reverseWords(s string) string { // 去除字符串两端的空格 s = strings.TrimSpace(s) // 递归反转单词 reversed := reverseWordsRecursive(s, len(s)-1) // 去除可能的首部空格（由于递归拼接时添加的） if len(reversed) > 0 && reversed[0] == ' ' { reversed = reversed[1:] } return reversed } func main() { s := "Let's code together " reversed := reverseWords(s) fmt.Println(reversed) // 输出 "s'teL edoc rehtegot" }
说明
在上面的Go示例中，
reverseWords函数是入口点，它首先去除输入字符串两端的空格，然后调用reverseWordsRecursive函数来递归地反转字符串中的每个单词。reverseRange是一个辅助函数，用于反转字符串中指定范围内的字符。在
reverseWordsRecursive函数中，我们找到最后一个单词的起始和结束位置，然后调用reverseRange来反转这个单词。之后，我们递归地对剩余部分的字符串进行相同的操作，并将反转后的单词与剩余部分拼接起来。最后，在
main函数中，我们调用reverseWords并打印出结果。请注意，这些代码示例是为了演示如何递归地反转字符串中的单词，并可能不是最优或最高效的解决方案。在实际应用中，可能需要考虑性能和内存使用情况，并相应地优化代码。
复杂度分析
- 时间复杂度：O(n)，其中 n 是字符串 s 的长度。遍历字符串和栈操作都是线性的。
- 空间复杂度：O(n)，在最坏情况下，栈中可能存储了整个字符串的字符或单词，因此需要额外的空间。
总结
| 方式 | 优点 | 缺点 | 时间复杂度 | 空间复杂度 |
| 方式一 | 直观且易于理解 | 在 Java 和 Python 中可能需要额外的空间 | O(n) | Java, Python, Golang: O(n), C: O(1) |
| 方式二 | 递归 | 实现相对复杂，可能导致栈溢出（在递归情况下） | O(n) | O(n) |
相似题目
请注意，上述相似题目和难度是基于 LeetCode 的分类和评级，并且可能随时间而有所变化。这些题目与反转字符串中的单词问题在字符串处理方面有一定的相关性，但解决方法和技术可能有所不同。
