# Question

Formatted question description: https://leetcode.ca/all/186.html

 186	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.

Could you do it in-place without allocating extra space?



# Algorithm

First flip each word, then the entire string,

Or you can reverse the order, first flip the entire string, and then flip each word.

# Code

Java

• 
public class Reverse_Words_in_a_String_II {

public void reverseWords(char[] s) {
reverse(s, 0, s.length);

int l = 0; // left
int r = 0; // right
while (r <= s.length) {
if (r == s.length || s[r] == ' ') {
reverse(s, l, r);
l = r + 1; // +1 to skip space
}

r++;
}
}

// end is exclusive
private void reverse(char[] s, int begin, int end) {
for (int i = 0; i < (end - begin) / 2; i++) {
char temp = s[begin + i];
s[begin + i] = s[end - i - 1];
s[end - i - 1] = temp;
}
}

}

• // OJ: https://leetcode.com/problems/reverse-words-in-a-string-ii/
// Time: O(N)
// Space: O(1)
class Solution {
public:
void reverseWords(vector<char>& s) {
int i = 0, N = s.size();
while (i < N) {
int start = i;
while (i < N && s[i] != ' ') ++i;
reverse(begin(s) + start, begin(s) + i);
++i;
}
reverse(begin(s), end(s));
}
};

• class Solution:
# @param s, a list of 1 length strings, e.g., s = ['h','e','l','l','o']
# @return nothing
def reverseWords(self, s):
def swap(start, end, slist):
while start < end:
slist[start], slist[end] = slist[end], slist[start]
start += 1
end -= 1

wstart, wend = 0, 0
for i in range(0, len(s)):
if s[i] == " ":
wend = i - 1
swap(wstart, wend, s)
wstart = i + 1
elif i + 1 == len(s):
swap(wstart, i, s)

swap(0, len(s) - 1, s)