# Reverse Words in a String II

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

Example:

``````Input:
["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]

Output:
["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]``````

Note:

• A word is defined as a sequence of non-space characters.

• The input string does not contain leading or trailing spaces.

• The words are always separated by a single space.

Follow up: Could you do itin-placewithout allocating extra space?

Topics: Two Pointers, String

## Analysis

`void reverseEachWords(char[] str)`中，快指针找到word结尾后的index，满指针指向word的开始第一个index。

## Solution

Two-Pointer + Multi-reversal - O(n) time, O(1) space (In-place) - (5ms AC)

``````class Solution {
public void reverseWords(char[] str) {
// reverse the whole input
reverse(str, 0, str.length - 1);

// reverse each individual word
reverseEachWords(str);
}

void reverse(char[] str, int s, int t) {
while (s < t) {
char tmp = str[s];
str[s] = str[t];
str[t] = tmp;
s++;
t--;
}
}

void reverseEachWords(char[] str) {
int i = 0, j = 0;
int n = str.length;
while (i < n && j < n) {
while (i < n && str[i] == ' ') {
i++;
}
j = i;
while (j < n && str[j] != ' ') {
j++;
}
reverse(str, i, j - 1);
i = j;
}
}
}``````

This solution (by @siyang3) takes advantage of the conditions in the problem: 1. The input string does not contain leading or trailing spaces. 2. The words are always separated by a single space.

``````public void reverseWords(char[] s){
reverseWords(s,0,s.length-1);
for(int i = 0, j = 0;i <= s.length;i++){
if(i==s.length || s[i] == ' '){
reverseWords(s,j,i-1);
j = i+1;
}
}
}

private void reverseWords(char[] s, int begin, int end){
while(begin < end){
char c = s[begin];
s[begin] = s[end];
s[end] = c;
begin++;
end--;
}
}``````

Last updated