# 151\_Reverse Words in a String

\[medium]

Given an input string, reverse the string word by word.

Note: need to make sure that the string only contains letters and spaces.

### Test case 1 (easy)

```
Input: "the weather is good"
Output: "good is weather the"
```

### Test case 2 (with spaces at the beginning and the end)

```
Input: "   the weather is good   "
Output: "good is weather the"
```

### Test case 3 (only spaces in the string)

```
Input: "      "
Output: ""
```

### Test case 4 (empty string)

```
Input: ""
Output: ""
```

### Test case 5 (more than one space between words)

```
Input: "the    weather    is     good"
Output: "good is weather the"
```

## _Idea 1_

* extract all words in to a list
* reverse the list
* join strings in the list with space

### Complexity 1

* Time: $$O(n)$$
* Space: $$O(n)$$

### Solution 1\_v1 (with build-in functions split(), reverse(),  join())

```python
class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """

        out = " ".join(reversed(s.split()))
        return out
```

### Solution 1\_v2 (write split(), use build in reverse(),  join())

```python
class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """

        out = []        
        word = ""

        # split the string into a list of words
        for i in range(len(s)) :
            # if current character is not space, add it to word
            # if current character is space，and word is not empty, 
            # append current word to out and set word to empty
            # otherwise, continue with next character
            if s[i] != " " :
                word += s[i]
            elif word != "" :
                out.append(word)
                word = ""
            else :
                continue

        # if sting is not empty and last character is not space,
        # add current word to out
        if len(s) > 0 and s[-1] != " " :
            out.append(word)

        # reverse the list, then join with space
        return " ".join(reversed(out))
```

## _Idea 2_

* reverse the entire string
* loop over the string, reverse the words, append space after each word, and neglect all the spaces.

### Complexity 2

* Time: $$O(n)$$
* Space: $$O(n)$$&#x20;

### Solution 2

```python
class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """

        # current word
        word = ""
        # output reversed string
        out = ""

        # reverse input string
        s = s[ : :-1]

        for i in range(len(s)) :
            # For first letter in words except the first word, 
            # put the current stored word into out, let current word be the current letter.
            if s[i] != " " and s[i-1] == " " and word != "":
                out += word + " "
                word = s[i] 
            # For all other letters, update current word in a reversed order.
            elif s[i] != " " :
                word = s[i] + word
            # Skip all the spaces.
            else :
                continue
        # store the last word
        out += word
        return out
```

## _Idea 3_

* reverse the entire string
* loop over the string, reverse the words, append space after each word, and neglect all the spaces.
* do everything in-place

### Complexity 3

* Time: $$O(n)$$
* Space: $$O(1)$$&#x20;

```python
def reverseWords(s):
    """
    :type s: str
    :rtype: str
    """
    if s == "": return s
    s = list(s)

    # reverse the input string first
    s.reverse()

    # reverse each word
    start, end = 0, 0
    while end < len(s):
        if not s[end] == " ":
            end += 1
        elif start < end:
            # just finish one word
            s[start:end] = reversed(s[start:end])
            end += 1
            start = end
        elif start == end:  
            # the string starts with space or
            # there are multiple spaces between words
            s.pop(end)
    if start < end:
        # the last word is not reversed yet
        s[start:end] = reversed(s[start:end])
    if len(s) >= 1 and s[-1] == " ":
        # the string ends with space
        s.pop()
    return "".join(s)
```
