【LeetCode 中等题】79-翻转字符串里的单词

 题目描述：给定一个字符串，逐个翻转字符串中的每个单词。

示例:  

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

说明:

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

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

解法1。利用python里对字符串的切片、逆转的方便操作，very pythonic

class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """
        if not s:
            return ''
        return ' '.join(reversed(s.split()))
           

解法2。思路同上面的解法，就是用一个指针i定位每个单词的首末位置，放到res中，最后返回res逆序后的连接

class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """
        if not s:
            return ''
        i = 0
        len_s = len(s)
        res = []
        while i < len_s:
            while i <len_s and s[i] == ' ':
                i += 1
            if i >= len_s:
                break
            start = i
            while i < len_s and s[i] != ' ':
                i += 1
            end = i
            res.append(s[start:end])
        return ' '.join(reversed(res))
           

解法3。先对s做一定预处理，去掉首尾空格，split后作为列表存在（一来可以去掉单词之间多余的空格，二来列表可以原地改变，便于后续交换元素）。然后逆转再遍历，遍历时，遇到是单词就原地逆转该单词，最后返回join后的结果

• 空间复杂度O(1)，原地修改

class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """
        s = s.strip()
        if not s:
            return ''
        i = 0
        s = ' '.join(s.split())
        s = list(s)
        len_s = len(s)
        self.reverse_s(s, 0, len_s-1)
        while i < len_s:
            while i < len_s and s[i] ==' ':
                i += 1
            if i >= len_s:
                break
            start = i
            while i < len_s and s[i] != ' ':
                i += 1
            end = i
            self.reverse_s(s, start, end-1)
        return ''.join(s)
            
    def reverse_s(self, s, start, end):
        if start != end:
            while start < end:
                s[start], s[end] = s[end], s[start]
                start += 1
                end -= 1