Reverse Words in a String

1public String reverseWords(String s) {
2    char[] chars = s.toCharArray();
3    int n = chars.length;
4
5    // Step 1: Reverse entire string
6    reverse(chars, 0, n - 1);
7
8    // Step 2: Reverse each word
9    int start = 0;
10    for (int i = 0; i <= n; i++) {
11        if (i == n || chars[i] == ' ') {
12            if (i > start) {
13                reverse(chars, start, i - 1);
14            }
15            start = i + 1;
16        }
17    }
18
19    // Step 3: Clean up spaces
20    int write = 0;
21    int i = 0;
22    while (i < n) {
23        if (chars[i] != ' ') {
24            if (write != 0) {
25                chars[write++] = ' ';
26            }
27            while (i < n && chars[i] != ' ') {
28                chars[write++] = chars[i++];
29            }
30        }
31        i++;
32    }
33
34    return new String(chars, 0, write);
35}
36
37private void reverse(char[] chars, int left, int right) {
38    while (left < right) {
39        char temp = chars[left];
40        chars[left] = chars[right];
41        chars[right] = temp;
42        left++;
43        right--;
44    }
45}