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)
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)
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[0];
}
}