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?
思路：
要求是否可以不需要额外空间，即只在原来的char数组上操作。
首先可以把整个char数组反转，然后再对每个单词进行反转。
反转可以用一个函数reverse实现。
找每个需要反转的单词可以通过双指针结合游标的方式实现。
public void reverseWords(char[] str) {
if (str == null || str.length == 0) {
return;
}
reverse(str, 0, str.length - 1);
//寻找单词的双指针，i是游标
int wordStart = 0, wordEnd = 0;
for (int i = 0; i < str.length; i++) {
if (str[i] != ' ') {
wordEnd = i;
}
if (str[wordStart] == ' ' && str[i] != ' ') {
wordStart = i;
}
if (str[i] == ' ' || i == str.length - 1) {
if (str[wordStart] != ' ' && str[wordEnd] != ' ') {
reverse(str, wordStart, wordEnd);
wordStart = wordEnd = i + 1;
}
}
}
}
private void reverse(char[] str, int start, int end) {
while (start < end) {
char tmp = str[start];
str[start++] = str[end];
str[end--] = tmp;
}
}
