Reverse Words in a String II

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 itin-placewithout allocating extra space?

Topics: Two Pointers, String

Analysis

分析见Reverse Words in a String

同样是多步翻转+Two Pointer进行逆序、翻转操作。

在void reverseEachWords(char[] str)中，快指针找到word结尾后的index，满指针指向word的开始第一个index。

Solution

Two-Pointer + Multi-reversal - O(n) time, O(1) space (In-place) - (5ms AC)

class Solution {
    public void reverseWords(char[] str) {
        // reverse the whole input 
        reverse(str, 0, str.length - 1);

        // reverse each individual word
        reverseEachWords(str);
    }

    void reverse(char[] str, int s, int t) {
        while (s < t) {
            char tmp = str[s];
            str[s] = str[t];
            str[t] = tmp;
            s++;
            t--;
        }
    }

    void reverseEachWords(char[] str) {
        int i = 0, j = 0; 
        int n = str.length;
        while (i < n && j < n) {
            while (i < n && str[i] == ' ') {
                i++;
            }
            j = i;
            while (j < n && str[j] != ' ') {
                j++;
            }
            reverse(str, i, j - 1);
            i = j;
        }
    }
}

This solution (by @siyang3) takes advantage of the conditions in the problem: 1. The input string does not contain leading or trailing spaces. 2. The words are always separated by a single space.

public void reverseWords(char[] s){
    reverseWords(s,0,s.length-1);
    for(int i = 0, j = 0;i <= s.length;i++){
        if(i==s.length || s[i] == ' '){
            reverseWords(s,j,i-1);
            j = i+1;
        }
    }
}

private void reverseWords(char[] s, int begin, int end){
    while(begin < end){
        char c = s[begin];
        s[begin] = s[end];
        s[end] = c;
        begin++;
        end--;
    }
}