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實現(xiàn)喻喳。
找每個需要反轉的單詞可以通過雙指針結合游標的方式實現(xiàn)耻陕。
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;
}
}
