Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.
The input string does not contain leading or trailing spaces and the words are always separated by a single space.
For example,
Given s = "the sky is blue",
return "blue is sky the".
Could you do it in-place without allocating extra space?
Solution：整体reverse + every words reverse
思路： 和//www.greatytc.com/p/5e74b3826441相同，只不过输入的是char[]型，可以修改，则不需要新建result数组， No extra space
Time Complexity: O(N) Space Complexity: O(1)
Solution Code：
public class Solution {
public void reverseWords(char[] s) {
// 1, reverse the whole sentence
reverse(s, 0, s.length - 1);
// 2, reverse each word
int start = 0;
for (int i = 0; i < s.length; i++) {
if (s[i] == ' ') {
reverse(s, start, i - 1);
start = i + 1;
}
}
// 3, Corner Case: reverse the last word
reverse(s, start, s.length - 1);
}
public void reverse(char[] s, int i, int j) {
while (i < j) {
char t = a[i];
a[i++] = a[j];
a[j--] = t;
}
}
}
