# Reverse Words in a String

#1

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

Example:

```Input: "`the sky is blue`",
Output: "`blue is sky the`".
```

Note:

• A word is defined as a sequence of non-space characters.
• 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.

Follow up: For C programmers, try to solve it in-place in O(1) space.

#2

The below does two things.

• Reverse the whole string first.
• Copy each word to the start and reverse it. This will take care of more than one space between words.
``````public class Solution {
public String reverseWords(String s) {
if (s == null) {
return null;
}
char[] str = s.toCharArray();

// reverse the whole string first
reverse(str, 0, str.length - 1);
int index = 0;
// here we copy over each word to the start and reverse each of them.
for(int i=0;i<str.length;i++){
if (str[i] != ' ') {
// start of a new word, so we add the space
if(index != 0){
str[index++] = ' ';
}

int j=i;
while(j<str.length && str[j]!=' '){
str[index++] = str[j++];
}
// index-(j-i) coz we want to know how much did index move. so current position of index
// minus how much "j" moved since it was "i"
reverse(str, index-(j-i), index-1);
i=j;
}
}

// finally return the sub string from 0 to index.
return new String(str).substring(0, index);
}

public void reverse(char[] str, int i, int j) {
while (i < j) {
char tem = str[i];
str[i++] = str[j];
str[j--] = tem;
}
}
}
``````

#3

Starting from the end, adding all valid words.

``````public class Solution {
public String reverseWords(String s) {
if(s==null || s.length()==0) return "";
StringBuilder result = new StringBuilder();
for(int i=s.length()-1;i>=0;i--){
if(s.charAt(i)!=' '){
int j=i;
while(j>=0 && s.charAt(j)!=' ') j--;
result.append(' ');
result.append(s.substring(j+1, i+1));
i = j;
}
}

return result.toString().trim();
}
}
``````