Reverse Words in a String I && I

（151、186 Medium）

Given an input string, reverse the string word by word.

For example,
Given s = "the sky is blue",

return "blue is sky the".

I可用使用额外空间。

II要求in-place，也就是说不需要开辟额外空间

双指针交换法

复杂度

时间 O(N) 空间 O(N) 如果输入时char数组则是O(1)

public String reverseWords(String s) {
    s = s.trim();
    char[] str = s.toCharArray();
    // 先反转整个数组
    reverse(str, 0, str.length - 1);
    int start = 0, end = 0;
    for(int i = 0; i < s.length(); i++){
        if(str[i]!=' '){
            end++;
        } else {
            //反转每个单词,这时end指向空格
            reverse(str, start, end - 1);
            end++;
            start = end;
        }
    }
    return String.valueOf(str);
}

public void reverse(char[] str, int start, int end){
    while(start < end){
        char tmp = str[start];
        str[start] = str[end];
        str[end] = tmp;
        start++;
        end--;
    }
}