151. Reverse Words in a String

link

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

Example 1:

Input: "the sky is blue"
Output: "blue is sky the"

Example 2:

Input: "  hello world!  "
Output: "world! hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Note:

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

• Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.

• You need to reduce multiple spaces between two words to a single space in the reversed string.

Follow up:

For C programmers, try to solve it in-place in O(1) extra space.

Soltution

To solve string/array problem like this, we can use two pointer ( usually one is always faster than another)

Since our goal is to speperate the whole String into small piece of word, and reverse them individually. we need to find out the boundary of each word.

the format will be like

int slow = 0, fast = 0;

while ( slow < n)
{
    while( slow < fast || !(boundary condition for slow)) slow++;
    while( fast < slow || !(boundary condition for fast)) fast++;
    //after the two loop, slow & fast satisfied bounary condition

}

    public String reverseWords(String s) {
        char[] chars = s.toCharArray();
        int from = 0;
        int end = chars.length - 1;
        
        reverse(chars, from, end);
        reverseWord(chars);
        String ns = removeSpace(chars);
        return ns;
        
    }
    
    public String removeSpace(char[] s){
        int i = 0, j = 0;
        int n = s.length;
        while(i < n){
        
            // regard __xxx__ as a sub-question we want to handle
            while(i < n && s[i] == ' ') i++;
            while(i < n && s[i] != ' ') s[j++] = s[i++];
            while(i < n && s[i] == ' ') i++;
            //means that we found a i in [0...n] that a[i] is non space.
            //we need to add back the space before we add next word
            if(i < n){
                s[j++] = ' ';
            }
        }
        return new String(s).substring(0, j);
    }
    
    public void reverseWord(char[] s){
        int i = 0, j = 0;
        int n = s.length;
        while(i < n){
            //to find the i, j which nums[i] is not space and nums[j] is space and j > i
            while(i < j || i < n && s[i] == ' ') i++;
            while(j < i || j < n && s[j] != ' ') j++; 
            
            reverse(s, i, j-1);
        }   
    }
    
    public void reverse(char[] s, int from, int end){
        char temp = ' ';
        while(from < end){
            temp = s[from];
            s[from] = s[end];
            s[end] = temp;
            from++;
            end--;
        }        
    }