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