186. Reverse Words in a String II

Description

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

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?

Constraints

Approach

Reverse the Whole String and Then Reverse Each Word

Links

• GeeksforGeeks

• Leetcode
• ProgramCreek
• YouTube

Examples

Example 1

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

Solutions

Solution 1

/**
 * Time complexity : O(N), it's two passes along the string.
 * Space complexity : O(1), it's a constant space solution.
 */

class Solution {
    public void reverseWords(char[] s) {
        if(s == null || s.length == 0) return;
        
        // reverse the whole string
        reverse(s, 0, s.length-1);
        
        // reverse each word
        reverseEachWord(s);
    }
    
    private void reverse(char[] chars, int left, int right) {
        while(left < right) {
            char tmp = chars[left];
            chars[left++] = chars[right];
            chars[right--] = tmp;
        }
    }
    
    private void reverseEachWord(char[] chars) {
        int n = chars.length;
        int start = 0, end = 0;
        
        while(start < n) {
            // go to the end of the word
            while(end < n && chars[end] != ' ') {
                end++;
            }
            // reverse the word
            reverse(chars, start, end-1);
            // move to the next word
            end++;
            start = end;
        }
    }
}

Follow up