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?
Related problem: Rotate Array
O(n) runtime, O(1) space – In-place reverse:
Let us indicate the ith word by wi and its reversal as wi′. Notice that when you reverse a
word twice, you get back the original word. That is, (wi′)′ = wi.
The input string is w1 w2 ... wn. If we reverse the entire string, it becomes wn′ ... w2′ w1′. Finally, we reverse each individual word and it becomes wn ... w2 w1. Similarly, the same result could be reached by reversing each individual word first, and then reverse the entire string.
1 public void reverseWords(char[] s) { 2 reverse(s, 0, s.length); 3 for(int i = 0, j = 0; j <= s.length; j++) { 4 if(j == s.length || s[j] == ‘ ‘) { 5 reverse(s, i, j); 6 i = j + 1; 7 } 8 } 9 } 10 public void reverse(char[] s, int start, int end) { 11 for(int i = 0; i < (end - start)/2; i++) { 12 char temp = s[start + i]; 13 s[start + i] = s[end - i- 1]; 14 s[end - i - 1] = temp; 15 } 16 }
Reverse Words in a String II(leetcode186)
原文：http://www.cnblogs.com/caomeibaobaoguai/p/4893591.html