跳转至

LeetCode: 151. 翻转字符串里的单词

1、题目描述

给定一个字符串,逐个翻转字符串中的每个单词。

示例:

输入: "the sky is blue",
输出: "blue is sky the".

说明:

  • 无空格字符构成一个单词。
  • 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。
  • 如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。

进阶: 请选用C语言的用户尝试使用 O(1) 时间复杂度的原地解法。

2、解题思路

​ 如果用python,当然是很简单就做出来了,不过题目要求如果用C的话,就写一下基本思路好了

​ 一遍扫描肯定是不好做的,因为还不知道单词的分界线

​ 分两步

  • 预处理,将单词反转,并去掉多余的空格
  • 整个数组反转,找到头结点,返回

示例

"the sky is blue"
上面是输入,我们两个指针,第一个指向单词的首部,第二个指向尾部,找到单词以后,反转,然后放到头上
"eht sky is blue"
如果有多个空格,只保留一个即可
扫描到最后,整个数组应该长成这样子
"eht yks si eulb"
然后,整个数组反转
就得到结果了
"blue is sky the"

基本思路就是这样,需要注意返回的位置

下面直接用python做一下

class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """
        return " ".join(reversed([v for v in s.split(" ") if v != ""]))

​ 用C语言要写这么多,用python只有一行,哈哈哈,超过99.29%,其实没差了