每日一题：LeetCode-151. 反转字符串中的单词

作者：半亩房顶

2023-12-08
北京
本文字数：1737 字
阅读完需：约 6 分钟

刷题使我快乐，满脸开心.jpg

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/reverse-words-in-a-string/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

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

进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。

思路

还没看到进阶时候，第一反应就是起一个新字符串，先处理掉多余的空格，然后整体反转后，再反转一个个单词即可。但是看到进阶之后，自然是要接受挑战了。

Go的字符串不能直接用下标定位赋值，所以需要先转成byte数组。其实Go中这个强转过程会发生拷贝（可以打印地址验证下），也就是空间复杂度其实并不符合。不过想要实现无拷贝转换需要使用unsafe包，感觉这里就不纠结这个问题了，主要是看下思路~

去除多余空格

开始我尝试在一次遍历中兼顾反转和过滤空格，不过发现心智负担太高，暂时搞不定，所以拆解成两个步骤，先去掉多余的空格。

多余就是指头尾空格，和单词之间多于一个的空格

头尾不用多说，主要问题就是在于中间空格的处理了。这里很常用的办法就是双指针法了。

快指针先跨过头部空格
后续只往慢指针处赋予非空格和第一个空格，直到结束
直到结束遍历，尾部至多留有一个空格，再行判断去除即可

反转

反转就简单多了，直接首尾两个指针对向移动，交换元素直到相遇

思路差不多就这样了，细节在代码注释了，上代码~

代码

个人递归解法

func reverseWords(s string) string {    sBytes := []byte(s)
    // 使用双指针去除空格    slow, fast := 0, 0    // 头部空格部分等待被实际内容替换即可，无需现在处理    for fast < len(sBytes) && sBytes[fast] == ' ' {        fast++    }    for fast < len(sBytes) {        // 非空格或者第一个空格，需要填充到头部        if sBytes[fast] != ' ' ||            (sBytes[fast] == ' ' && sBytes[fast-1] != ' ') {            sBytes[slow] = sBytes[fast]            fast++            slow++        } else if sBytes[fast] == ' ' && sBytes[fast-1] == ' ' {            // 中间多余的空格，需要跳过            fast++        }    }    // 看最后一个放进去的是不是空格，有则说明尾部有空格，截掉它    if slow > 0 && sBytes[slow-1] == ' ' {        sBytes = sBytes[:slow-1]    } else {        sBytes = sBytes[:slow]    }
    // 整体反转字符串    reverse(&sBytes, 0, len(sBytes)-1)
    // 逐步反转每个单词    start, end := -1, -1    // 把超出数组的下标放进来，兼容最后一个单词的情况    for i := 0; i <= len(sBytes); i++ {        // 最后一个单词的情况，外加遇到空格时，就是扫描到了一个单词，需要执行单词反转        if i == len(sBytes) || sBytes[i] == ' ' {            end = i - 1            reverse(&sBytes, start, end)            start = -1            end = 0        } else if sBytes[i] != ' ' && start == -1 {            // start未赋值时，第一次非空格就是新单词的起点            start = i        }    }    return string(sBytes)}
func reverse(s *[]byte, start, end int) {    for start < end {        (*s)[start], (*s)[end] = (*s)[end], (*s)[start]        start++        end--    }}

复制代码

发布于: 刚刚阅读数: 5

原文链接:【http://xie.infoq.cn/article/a13de41b56ccee29b2fb5ef6e】。文章转载请联系作者。

半亩房顶

关注

人生那么长，能写多少bug？ 2018-11-16 加入

我希望，自己永远是自己。我希望，远离bug。

发布

暂无评论

创作场景

每日一题：LeetCode-151. 反转字符串中的单词

题目

思路

去除多余空格

反转

代码

个人递归解法

半亩房顶

评论