151.md

Solution 1

1-line in python

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

Solution 2

def reverseWords(s):
    stack = []
    tmp = ''
    s += ' '
    # split manually
    for i in range(len(s)):
        if s[i] == ' ':
            if tmp:
                stack.append(tmp)
                tmp = ''
        else:
            tmp += s[i]

    if not stack:
        return ""

    # res = stack.pop()
    # while stack:
    #     res += " "
    #     res += stack.pop()
    #
    # return res
    return ' '.join(stack[::-1])

Solution 3

If we don't want to reduce multiple space.

1. reverse all chars
2. reverse each word

def reverseWords(self, s: str) -> str:
    def reverse(s, l, r):
        i, j = l, r
        while i < j:
            s[i], s[j] = s[j], s[i]
            i += 1
            j -= 1

    # s += ' '
    stri = list(s)
    reverse(stri, 0, len(s)-1)
    # stri.append(' ')

    start = -1
    for i in range(len(stri)):
        if stri[i] == ' ':
            # meet end of a word 
            if start >= 0:
                reverse(stri, start, i-1)
                start = -1
        # start of a word 
        elif start < 0:
            start = i
    # reverse the last word 
    if start >= 0: reverse(stri, start, len(stri)-1)

    return ''.join(stri)

Furthermore, to reduce multiple space

def reverseWords(s):
    if not s: return s
    startIdx = 0
    stri = list(s)
    reverse(stri, 0, len(stri) - 1)

    # for i in range(len(stri)):
    i = 0
    while i < len(stri):
        if stri[i] != ' ':
            if startIdx != 0:
                stri[startIdx] = ' '
                startIdx += 1
            j = i
            while j < len(stri) and stri[j] != ' ':
                stri[startIdx] = stri[j]
                startIdx += 1
                j += 1
            self.reverse(stri, startIdx - (j - i), startIdx - 1)

            i = j
        i += 1
    return ''.join(stri[:startIdx])

def reverse(s, i, j):
    while i < j:
        s[i], s[j] = s[j], s[i]
        i += 1
        j -= 1