LeetCode 557. 反转字符串中的单词 III

Categories:

题目描述
思路分析
1. 解法一：按空格分割后逐词反转（推荐）
2. 解法二：双指针原地反转每个单词
相似题目

题目描述

✅ 557. 反转字符串中的单词 III

思路分析

解法一：按空格分割后逐词反转（推荐）

核心思路：

以空格为分隔符将字符串拆分为单词数组。

对每个单词单独执行字符反转。

将反转后的单词重新拼接，以空格连接输出。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串的长度，每个字符最多被访问两次。

空间复杂度：O(n)，需要额外存储拆分后的单词数组及结果字符串。

class Solution {
    public String reverseWords(String s) {
        // 按空格拆分为单词数组
        String[] words = s.split(" ");
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < words.length; i++) {
            // 反转当前单词并追加
            sb.append(reverseWord(words[i]));
            if (i < words.length - 1) {
                sb.append(" ");
            }
        }
        return sb.toString();
    }

    private String reverseWord(String word) {
        // 双指针对调首尾字符
        char[] chars = word.toCharArray();
        int left = 0, right = chars.length - 1;
        while (left < right) {
            char tmp = chars[left];
            chars[left] = chars[right];
            chars[right] = tmp;
            left++;
            right--;
        }
        return new String(chars);
    }
}

func reverseWords(s string) string {
    // 按空格拆分为单词切片
    words := strings.Fields(s)
    for i := 0; i < len(words); i++ {
        // 对每个单词执行字符反转
        words[i] = reverseWord(words[i])
    }
    return strings.Join(words, " ")
}

func reverseWord(s string) string {
    // 转为 rune 切片以正确处理多字节字符
    runes := []rune(s)
    left, right := 0, len(runes)-1
    for left < right {
        runes[left], runes[right] = runes[right], runes[left]
        left++
        right--
    }
    return string(runes)
}

解法二：双指针原地反转每个单词

核心思路：

将字符串转为字符数组，通过双指针在原数组上定位每个单词的起止边界。

找到单词的左右边界后，用双指针对调字符完成反转，无需额外拆分数组。

适合对空间有严格要求的场景，逻辑更紧凑。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串的长度，每个字符最多被访问两次。

空间复杂度：O(n)，Java/Go 中字符串不可变，需转为字符数组处理。

class Solution {
    public String reverseWords(String s) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        int start = 0;
        for (int i = 0; i <= n; i++) {
            // 遇到空格或到达末尾时，反转 [start, i-1] 范围内的单词
            if (i == n || chars[i] == ' ') {
                reverse(chars, start, i - 1);
                start = i + 1;
            }
        }
        return new String(chars);
    }

    private void reverse(char[] chars, int left, int right) {
        // 双指针对调首尾字符
        while (left < right) {
            char tmp = chars[left];
            chars[left] = chars[right];
            chars[right] = tmp;
            left++;
            right--;
        }
    }
}

func reverseWords(s string) string {
    // 字符串转为字节切片，便于原地修改
    b := []byte(s)
    n := len(b)
    start := 0
    for i := 0; i <= n; i++ {
        // 遇到空格或到达末尾时，反转当前单词
        if i == n || b[i] == ' ' {
            reverseBytes(b, start, i-1)
            start = i + 1
        }
    }
    return string(b)
}

func reverseBytes(b []byte, left, right int) {
    // 双指针对调首尾字节
    for left < right {
        b[left], b[right] = b[right], b[left]
        left++
        right--
    }
}

相似题目

题目	难度	考察点
344. 反转字符串	简单	双指针、字符串反转
541. 反转字符串 II	简单	双指针、字符串分段反转
151. 反转字符串中的单词	中等	双指针、字符串处理
186. 颠倒字符串中的单词 II	中等	双指针、原地反转
917. 仅仅反转字母	简单	双指针、字符串处理
58. 最后一个单词的长度	简单	字符串遍历

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/77137837