186. Reverse-Words-in-a-String-II

difficulty: Medium

section pre{ background-color: #eee; border: 1px solid #ddd; padding:10px; border-radius: 5px; }

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

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"]

Note:

• A word is defined as a sequence of non-space characters.

• The input string does not contain leading or trailing spaces.

• The words are always separated by a single space.

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

Method One

class Solution {
    private char[] chars;
    public void reverseWords(char[] s) {
        this.chars = s;
        reverse(0, s.length - 1);
        int left = 0;
        for(int i = 0; i < chars.length; i++ ) {
            if( chars[i] == ' ') {
                reverse(left, i - 1);
                left = i + 1;
            }
        }
        reverse(left, chars.length - 1);
    }
    public void reverse(int start , int end) {
        while(start < end ) {
            swap(start++, end--);
        }
    }
    public void swap(int i , int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }
}
​