[LintCode] Problem 927 - Reverse Words in a String II

Posted on | In ,

Given an input character array, reverse the array word by word. A word is defined as a sequence of non-space characters.

The input character array does not contain leading or trailing spaces and the words are always separated by a single space.

Example

Input: [“t”,”h”,”e”,” “,”s”,”k”,”y”,” “,”i”,”s”,” “,”b”,”l”,”u”,”e”]

Output: [“b”,”l”,”u”,”e”,” “,”i”,”s”,” “,”s”,”k”,”y”,” “,”t”,”h”,”e”]

Challenge

Could you do it in-place without allocating extra space?

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public char[] reverseWords(char[] str) {
    reverse(str, 0, str.length - 1);

    for (int i = 0; i < str.length;) {
        int j = i + 1;

        for (; j < str.length; j++) {
            if (str[j] == ' ')
                break;
        }

        reverse(str, i, j - 1);

        i = j + 1;
    }

    return str;
}

private void reverse(char[] str, int start, int end) {
    while (start < end) {
        char temp = str[end];
        str[end] = str[start];
        str[start] = temp;

        start++;
        end--;
    }
}