# Reverse Words in a String

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 itin-place_in_O(1) space.

Topics: Two Pointers, String

## Analysis

It actually reminds me of the string rotation problem , which could be solved by multi-step reversal of the string as well. The function `void reverseWords(char[] a, int n)`, which is very much similar to what could be used in Max Consecutive Ones problem.

Two Pointers to the MAX.

#### Multi-reversal

``````        // step 1. clean up spaces
char[] a = cleanSpaces(c, m);
int n = a.length;
// step 2. reverse the whole string
reverse(a, 0, n - 1);
// step 3. reverse each word
reverseWords(a, n);
``````

The `void reverseWords(char[] a, int n)` and `char[] cleanSpaces(char[] a, int n)` as well as `void reverse(char[] a, int i, int j)` all utilizes two pointers technique to remove spaces and reverse string.

## Solution

Adapted Version - Two Pointers + multi-reversal: O(n) time, O(1) space (6ms)

``````public class Solution {
public String reverseWords(String s) {
if (s == null) return null;

char[] c = s.toCharArray();
int m = c.length;
// step 1. clean up spaces
char[] a = cleanSpaces(c, m);
int n = a.length;
// step 2. reverse the whole string
reverse(a, 0, n - 1);
// step 3. reverse each word
reverseWords(a, n);
return new String(a);
}

void reverseWords(char[] a, int n) {
int i = 0, j = 0;
while (i < n) {
while (i < n && a[i] == ' ') {
i++; // skip spaces
}
// i is now the first index in the non-space word

// update right pointer
j = i;
while (j < n && a[j] != ' ') {
j++; // skip non-spaces
}
// j is now the first space on the right of a word

// reverse the word we just found
reverse(a, i, j - 1);

// update left pointer
i = j;
}
}

// trim leading, trailing and multiple spaces
char[] cleanSpaces(char[] a, int n) {
int i = 0, j = 0;

while (i < n && j < n) {
while (j < n && a[j] == ' ') {
j++; // skip spaces
}
while (j < n && a[j] != ' ') {
a[i++] = a[j++]; // copy non-spaces
}
while (j < n && a[j] == ' ') {
j++; // skip spaces
}
if (j < n) {
a[i++] = ' '; // append only one space
}
}

return Arrays.copyOf(a, i);
}

// reverse a[] from a[i] to a[j]
private void reverse(char[] a, int i, int j) {
while (i < j) {
char t = a[i];
a[i++] = a[j];
a[j--] = t;
}
}
}
``````

Multi-reverse + Two Pointers - O(n) time, O(1) space (7ms)

https://leetcode.com/problems/reverse-words-in-a-string/discuss/47720/Clean-Java-two-pointers-solution-(no-trim(-)-no-split(-)-no-StringBuilder\

``````public class Solution {
public String reverseWords(String s) {
if (s == null) return null;

char[] a = s.toCharArray();
int n = a.length;

// step 1. reverse the whole string
reverse(a, 0, n - 1);
// step 2. reverse each word
reverseWords(a, n);
// step 3. clean up spaces
return cleanSpaces(a, n);
}

void reverseWords(char[] a, int n) {
int i = 0, j = 0;
while (i < n) {
while (i < n && a[i] == ' ') {
i++; // skip spaces
}
// i is now the first index in the non-space word

// update right pointer
j = i;
while (j < n && a[j] != ' ') {
j++; // skip non-spaces
}
// j is now the first space on the right of a word

// reverse the word we just found
reverse(a, i, j - 1);

// update left pointer
i = j;
}
}

// trim leading, trailing and multiple spaces
String cleanSpaces(char[] a, int n) {
int i = 0, j = 0;

while (j < n) {
while (j < n && a[j] == ' ') j++;             // skip spaces
while (j < n && a[j] != ' ') a[i++] = a[j++]; // keep non spaces
while (j < n && a[j] == ' ') j++;             // skip spaces
if (j < n) a[i++] = ' ';                      // keep only one space
}

return new String(a).substring(0, i);
}

// reverse a[] from a[i] to a[j]
private void reverse(char[] a, int i, int j) {
while (i < j) {
char t = a[i];
a[i++] = a[j];
a[j--] = t;
}
}
}
``````

Using String operations `trim()`, `split()`- (65ms AC)

https://leetcode.com/problems/reverse-words-in-a-string/discuss/47706/My-accepted-Java-solution

``````public class Solution {
public String reverseWords(String s) {
String[] parts = s.trim().split("\\s+");
String out = "";
for (int i = parts.length - 1; i > 0; i--) {
out += parts[i] + " ";
}
return out + parts;
}
}
``````