# Reverse the String

Given a string A.

Return the string A after reversing the string word by word.

NOTE:

1. A sequence of non-space characters constitutes a word.

2. Your reversed string should not contain leading or trailing spaces, even if it is present in the input string.

3. If there are multiple spaces between words, reduce them to a single space in the reversed string.

Input Format

```The only argument given is string A.
```
Output Format

```Return the string A after reversing the string word by word.
```
For Example

```Input 1:
A = "the sky is blue"
Output 1:
"blue is sky the"

Input 2:
A = "this is ib"
Output 2:
"ib is this"```
Method:

First we reverse the entire string, then we reverse the words one by one

Solution:

Time: O(n)
Space: O(n)

public class Solution {
public String solve(String A) {
StringBuilder result = new StringBuilder();
char[] arr = A.toCharArray();
int start = 0;
int end = arr.length - 1;
reverse(arr, start, end);
while (arr[start] == ' ') start ++;
while (arr[end] == ' ') end --;
int i = start;
int j = start;
while (j <= end + 1) {
while (j <= end && arr[j] != ' ') j ++;
reverse(arr, i, j - 1);
result.append(new String(arr, i, j - i));
if (j != end + 1) {
result.append(" ");
} else {
break;
}
while (j <= end && arr[j] == ' ') j ++;
i = j;
}
return result.toString();
}

private void reverse(char[] arr, int left, int right) {
while (left < right) {
char tmp = arr[left];
arr[left] = arr[right];
arr[right] = tmp;
left ++;
right --;
}
}
}