151.翻转字符串里的单词

https://leetcode-cn.com/problems/reverse-words-in-a-string/

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

示例 1：

输入: "the sky is blue"

输出: "blue is sky the"

示例 2：

输入: " hello world! "

输出: "world! hello"

解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：

输入: "a good example"

输出: "example good a"

解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

说明：

• 无空格字符构成一个单词。

• 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

• 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

---

方法一

直接调用 Python 内置方法，先 strip 后 split 将字符串分割成数组，倒序后通过空格拼接即可

class Solution(object):

     def reverseWords(self, s):
         """
         :type s: str
         :rtype: str
         """
         return ' '.join(s.strip().split()[::-1])

当然本题考察的肯定不是对 Python 内置方法的使用，所以我们考虑自己完成字符串的翻转

方法二：

要实现题目中的要求我们需要考虑分四步走，首先将字符串转换成数组，以便于操作

• 字符串整体翻转

• 分别将各个单词翻转

• 处理前后空格

• 处理单词直接多余空格

class Solution(object):

    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """
        s_list = list(s)
        s_list = self.reverse_string(s_list, 0 , len(s) - 1)
        s_list = self.reverse_word(s_list)
        s_list = self.strip_side(s_list)
        s_list = self.strip_space(s_list)
        return ''.join(s_list)

    def reverse_string(self, s_list, l, r):
        while l < r:

        s_list[l], s_list[r] = s_list[r], s_list[l]
            l += 1
            r -= 1
        return s_list

    def reverse_word(self, s_list):
        """ 采用双指针定位单个单词起始位置 """

        l, r = 0, 0
        while r < len(s_list):
            while r < len(s_list) and not s_list[r].isspace():
                #: 此时 r 处在单个单词最后一个字符的下个空格位置，所以下面旋转时要减去 1
                r += 1
            self.reverse_string(s_list, l, r - 1)
            # 因为 r 目前所在位置为空格，往后移动一个位置，保证下个单词翻转后，单词直接至少有一个空格
            r += 1
            l = r
        return s_list

    def strip_side(self, s_list):
        l, r = 0, len(s_list) - 1
        while l < r and s_list[l].isspace():
            l += 1
        while l < r and s_list[r].isspace():
            #: while 跳出时，r 处在最后一个字符上，考虑到数组左闭右开的特性，下面要加 1
            r -= 1
        return s_list[l:r+1]

    def strip_space(self, s_list):
        if not s_list:
            return []
        res = [s_list[0]]
        for i in xrange(1, len(s_list)):
            # 想象一下，单个单词的最后一个字母被追加进数组后，下个空格被追加，然后就会满足while条件，跳过多余空格
            if res[-1].isspace() and s_list[i].isspace():
                continue
            res.append(s_list[i])
        return s_list