LeetCode如何翻转字符串里的单词

发布时间:2021-12-15 14:36:17 作者:小新
来源:亿速云 阅读:141
# LeetCode如何翻转字符串里的单词

## 问题描述

LeetCode第151题"翻转字符串里的单词"要求我们实现一个算法,将给定字符串中的单词顺序进行翻转,同时去除多余的空格。具体要求如下:

- 输入字符串可能包含前导空格、尾随空格和单词间的多个空格
- 返回的字符串应当单词顺序翻转,且单词间用单个空格分隔
- 不能使用任何内置的字符串处理函数(如split、reverse等)

示例:

输入: “ hello world ” 输出: “world hello”


## 解题思路分析

### 方法一:双指针法(最优解)

**核心思想**:先整体翻转字符串,再逐个翻转单词,最后处理空格

1. **去除多余空格**:使用快慢指针法去除字符串中多余的空格
2. **整体翻转**:将整个字符串进行翻转
3. **单词翻转**:识别每个单词的边界,对每个单词进行局部翻转
4. **调整格式**:确保单词间只有一个空格

**时间复杂度**:O(n)  
**空间复杂度**:O(1)(对于C++等可修改字符串的语言)

### 方法二:使用栈

**核心思想**:利用栈的先进后出特性实现翻转

1. 遍历字符串,提取单词并压入栈中
2. 依次弹出栈中单词组成新字符串
3. 处理空格问题

**时间复杂度**:O(n)  
**空间复杂度**:O(n)

### 方法三:分割+反转(不符合题目要求但实际常用)

虽然题目限制使用内置函数,但在实际开发中可以:
1. 使用split分割单词
2. 反转单词列表
3. 用join连接

## 代码实现(以方法一为例)

### Python实现
```python
def reverseWords(s: str) -> str:
    # 去除多余空格
    def trim_spaces(s):
        left, right = 0, len(s) - 1
        # 去掉首尾空格
        while left <= right and s[left] == ' ':
            left += 1
        while left <= right and s[right] == ' ':
            right -= 1
        
        # 去掉中间多余空格
        output = []
        while left <= right:
            if s[left] != ' ':
                output.append(s[left])
            elif output[-1] != ' ':
                output.append(s[left])
            left += 1
        return output
    
    # 反转字符数组
    def reverse(l, left, right):
        while left < right:
            l[left], l[right] = l[right], l[left]
            left += 1
            right -= 1
    
    # 反转每个单词
    def reverse_each_word(l):
        n = len(l)
        start = end = 0
        while start < n:
            # 找到单词末尾
            while end < n and l[end] != ' ':
                end += 1
            # 反转单词
            reverse(l, start, end - 1)
            # 更新指针
            start = end + 1
            end += 1
    
    # 主流程
    l = trim_spaces(s)
    reverse(l, 0, len(l) - 1)
    reverse_each_word(l)
    return ''.join(l)

Java实现

class Solution {
    public String reverseWords(String s) {
        // 去除空格
        StringBuilder sb = trimSpaces(s);
        // 翻转字符串
        reverse(sb, 0, sb.length() - 1);
        // 翻转每个单词
        reverseEachWord(sb);
        return sb.toString();
    }
    
    public 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;
    }
    
    public void reverse(StringBuilder sb, int left, int right) {
        while (left < right) {
            char tmp = sb.charAt(left);
            sb.setCharAt(left++, sb.charAt(right));
            sb.setCharAt(right--, tmp);
        }
    }
    
    public 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 + 1;
            end++;
        }
    }
}

边界条件与测试用例

常见测试用例

  1. 常规情况:
    • 输入:”the sky is blue”
    • 输出:”blue is sky the”
  2. 包含多个空格:
    • 输入:” hello world “
    • 输出:”world hello”
  3. 前后有空格:
    • 输入:” Bob Loves Alice “
    • 输出:”Alice Loves Bob”
  4. 单字单词:
    • 输入:”a good example”
    • 输出:”example good a”
  5. 全空格:
    • 输入:” “
    • 输出:””

特殊测试用例

  1. 空字符串:
    • 输入:””
    • 输出:””
  2. 连续多个空格:
    • 输入:”a b c d”
    • 输出:”d c b a”
  3. 单个单词:
    • 输入:“hello”
    • 输出:“hello”

算法优化与变种

优化点

  1. 字符串拼接优化:在Java中使用StringBuilder而非String直接拼接
  2. 原地修改:对于C++等语言可以直接修改原字符串
  3. 双指针优化:在去除空格时可以使用更高效的双指针法

相关问题变种

  1. 翻转字符串II(LeetCode 541):每隔2k字符翻转前k个
  2. 翻转字符串中的单词III(LeetCode 557):翻转每个单词但保持顺序
  3. 旋转字符串(LeetCode 796):检查是否可以通过旋转得到

常见错误与注意事项

  1. 空格处理不当
    • 忘记处理前导/尾随空格
    • 单词间保留多个空格
  2. 边界条件遗漏
    • 空字符串情况
    • 全空格字符串
  3. 原地修改问题
    • 在某些语言中字符串不可变,需要转换为数组
  4. 指针越界
    • 在双指针法中未正确处理指针移动

总结

翻转字符串中的单词是一个考察综合字符串处理能力的问题,涉及: 1. 字符串基本操作 2. 双指针技巧 3. 翻转操作实现 4. 边界条件处理

掌握这类问题有助于提升对字符串处理的整体理解,并为更复杂的算法问题打下基础。建议在理解基础解法后,尝试自己实现并考虑各种优化可能性。 “`

推荐阅读:
  1. leetcode--字符串翻转
  2. java实现翻转单词顺序列

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

leetcode

上一篇:CSS3变形技术有哪些

下一篇:LeetCode如何实现N叉树的前序遍历

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》