【经典算法】LeetCode 151. 反转字符串中的单词(Java/C/Python3实现含注释说明,中等)

简介: 【经典算法】LeetCode 151. 反转字符串中的单词(Java/C/Python3实现含注释说明,中等)

题目描述

给定一个字符串 s,反转字符串中每个单词的字符顺序,同时保留空格和单词的初始顺序。

示例 1:

输入: s = "Let's code in Python"
输出: "s'teL edoc ni nohtyP"

示例 2:

输入: s = "a good   example"
输出: "a doog   elpmaxe"

原题:151. 反转字符串中的单词

思路及实现

方式一:使用双指针反转字符串

思路

  1. 首先将字符串按空格分割成单词数组。
  2. 遍历单词数组,对每个单词使用双指针进行反转。
  3. 将反转后的单词重新拼接成字符串。

代码实现

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中使用StringBuilderreverse方法反转字符串,然后遍历单词数组,将反转后的单词依次添加到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. 递归地反转除最后一个单词之外的其他部分,并将反转后的结果与第1步中反转的最后一个单词连接起来。

具体步骤如下:

  1. 找到最后一个单词的起始位置:我们可以从字符串的末尾开始遍历,找到最后一个单词的起始位置。这通常是通过找到最后一个非空格字符的位置,然后向前遍历直到遇到空格或字符串的起始位置。
  2. 反转最后一个单词:使用双指针法,一个指针指向单词的起始位置,另一个指针指向单词的末尾位置,然后交换两个指针所指向的字符,直到两个指针相遇或交错。
  3. 递归处理剩余部分:将最后一个单词之后的所有字符(包括空格)作为新的字符串,递归调用反转函数。
  4. 拼接结果:将递归返回的结果与第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)

相似题目

相似题目 难度 链接
翻转字符串中的元音字母 简单 力扣-345
字符串转换整数 (atoi) 中等 力扣-8
验证回文字符串 简单 力扣-125
最长回文子串 中等 力扣-5

请注意,上述相似题目和难度是基于 LeetCode 的分类和评级,并且可能随时间而有所变化。这些题目与反转字符串中的单词问题在字符串处理方面有一定的相关性,但解决方法和技术可能有所不同。

相关文章
|
6天前
|
机器学习/深度学习 数据采集 搜索推荐
Python基于深度学习算法实现图书推荐系统项目实战
Python基于深度学习算法实现图书推荐系统项目实战
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
|
3天前
|
Java 开发者 Python
Python中,字符串(String)是一种不可变的数据类型
Python中,字符串(String)是一种不可变的数据类型
13 5
|
4天前
|
搜索推荐 C++ Python
Python排序算法大PK:归并VS快速,谁才是你的效率之选?
【7月更文挑战第13天】归并排序** 使用分治法,稳定且平均时间复杂度O(n log n),适合保持元素顺序和并行处理。
13 5
|
5天前
|
存储 算法 搜索推荐
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
【7月更文挑战第12天】归并排序是高效稳定的排序算法,采用分治策略。Python 实现包括递归地分割数组及合并已排序部分。示例代码展示了如何将 `[12, 11, 13, 5, 6]` 分割并归并成有序数组 `[5, 6, 11, 12, 13]`。虽然 $O(n log n)$ 时间复杂度优秀,但需额外空间,适合大规模数据排序。对于小规模数据,可考虑其他算法。**
25 4
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现WOA智能鲸鱼优化算法优化支持向量机分类模型(SVC算法)项目实战
Python实现WOA智能鲸鱼优化算法优化支持向量机分类模型(SVC算法)项目实战
|
4天前
|
存储 算法 Python
“解锁Python高级数据结构新姿势:图的表示与遍历,让你的算法思维跃升新高度
【7月更文挑战第13天】Python中的图数据结构用于表示复杂关系,通过节点和边连接。常见的表示方法是邻接矩阵(适合稠密图)和邻接表(适合稀疏图)。图遍历包括DFS(深度优先搜索)和BFS(广度优先搜索):DFS深入探索分支,BFS逐层访问邻居。掌握这些技巧对优化算法和解决实际问题至关重要。**
10 1
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现GBDT(梯度提升树)分类模型(GradientBoostingClassifier算法)并应用网格搜索算法寻找最优参数项目实战
Python实现GBDT(梯度提升树)分类模型(GradientBoostingClassifier算法)并应用网格搜索算法寻找最优参数项目实战
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现PCA降维和KNN人脸识别模型(PCA和KNeighborsClassifier算法)项目实战
Python实现PCA降维和KNN人脸识别模型(PCA和KNeighborsClassifier算法)项目实战