# Reverse Words in a String

Given an input string `s`, reverse the order of the words. A word is defined as a sequence of non-space characters. The words in `s` will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that `s` may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1:

```Input: s = "the sky is blue"
Output: "blue is sky the"```

Example 2:

```Input: s = "  hello world  "
Output: "world hello"

Example 3:

```Input: s = "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.```

Example 4:

```Input: s = "  Bob    Loves  Alice   "
Output: "Alice Loves Bob"```

Example 5:

```Input: s = "Alice does not even like bob"
Output: "bob like even not does Alice"```

Constraints:

• `1 <= s.length <= 104`
• `s` contains English letters (upper-case and lower-case), digits, and spaces `' '`.
• There is at least one word in `s`.

Note:

• A word is defined as a sequence of non-space characters.
• The input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
• You need to reduce multiple spaces between two words to a single space in the reversed string.

Here we consider two different solutions of linear time and space complexity:

1. Use built-in split and reverse. Benefits: in-place and the simplest one to write.
2. Two passes approach with a `Stack`. Move along the string, word by word, and push each new word in a `Stack`. Convert the `Stack` back into a string.

Approach 1: Built-in Split + Reverse:

```public String reverseWords(String s) {
s = s.trim();
// split by multiple spaces
List<String> wordList = Arrays.asList(s.split("\\s+"));
Collections.reverse(wordList);
return String.join(" ", wordList);
}
```

Complexity Analysis

• Time complexity: `O(N)`, where `N` is a number of characters in the input string.
• Space complexity: `O(N)`, to store the result of the split by spaces.

Approach 2: Stack of Words:

```public String reverseWords(String s) {
int left = 0;
int right = s.length() - 1;

while (left <= right) {
if (s.charAt(left) == ' ') {
left++;
} else break;
}

// remove trailing spaces
while (left <= right) {
if (s.charAt(right) == ' ') {
right--;
} else break;
}

StringBuilder word = new StringBuilder();
Stack<String> wordStack = new Stack<>();
while (left <= right) {
char current = s.charAt(left);
if (current != ' ') {
word.append(current);
} else {
if (word.length() > 0) {
String sWord = word.toString();
wordStack.push(sWord);
word = new StringBuilder();
}
}
left++;
}
if (word.length() > 0) {
String sWord = word.toString();
wordStack.push(sWord);
}
StringBuilder result = new StringBuilder();
while (wordStack.size() > 0) {
result.append(wordStack.pop());
if (wordStack.size() != 0) result.append(" ");
}
return result.toString();
}
```

Complexity Analysis

• Time complexity: `O(N)`, where `N` is a number of characters in the input string.
• Space complexity: `O(N)`, to store the result of the split by spaces.

Categories: String

Tagged as: ,