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?
Do it in place: reverse the whole string. For each subarray separated by ' ', reverse the subarray.
public void reverseWords(char[] s) {
if (s.length <= 1) {
return;
}
reverse(s, 0, s.length - 1);
int last = 0;
for (int i = 0; i < s.length; i++) {
if (s[i] == ' ') {
reverse(s, last, i - 1);
last = i + 1;
}
}
}
private void reverse(char[] s, int start, int end) {
while (start < end) {
char tmp = s[start];
s[start] = s[end];
s[end] = tmp;
start++;
end--;
}
}
No comments:
Post a Comment