Reverse Words in a String

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

Example:

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

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 itin-place_in_O(1) space.

Topics: Two Pointers, String

Analysis

It actually reminds me of the string rotation problem , which could be solved by multi-step reversal of the string as well. The function void reverseWords(char[] a, int n), which is very much similar to what could be used in Max Consecutive Ones problem.

Two Pointers to the MAX.

Multi-reversal

        // step 1. clean up spaces
        char[] a = cleanSpaces(c, m);
        int n = a.length;
        // step 2. reverse the whole string
        reverse(a, 0, n - 1);
        // step 3. reverse each word
        reverseWords(a, n);

The void reverseWords(char[] a, int n) and char[] cleanSpaces(char[] a, int n) as well as void reverse(char[] a, int i, int j) all utilizes two pointers technique to remove spaces and reverse string.

Solution

Adapted Version - Two Pointers + multi-reversal: O(n) time, O(1) space (6ms)

public class Solution {
    public String reverseWords(String s) {
        if (s == null) return null;

        char[] c = s.toCharArray();
        int m = c.length;
        // step 1. clean up spaces
        char[] a = cleanSpaces(c, m);
        int n = a.length;
        // step 2. reverse the whole string
        reverse(a, 0, n - 1);
        // step 3. reverse each word
        reverseWords(a, n);
        return new String(a);
    }

    void reverseWords(char[] a, int n) {
        int i = 0, j = 0;
        while (i < n) {
            while (i < n && a[i] == ' ') {
                i++; // skip spaces
            }
            // i is now the first index in the non-space word

            // update right pointer
            j = i;
            while (j < n && a[j] != ' ') {
                j++; // skip non-spaces
            }
            // j is now the first space on the right of a word

            // reverse the word we just found
            reverse(a, i, j - 1);

            // update left pointer
            i = j;
        }
    }

    // trim leading, trailing and multiple spaces
    char[] cleanSpaces(char[] a, int n) {
        int i = 0, j = 0;

        while (i < n && j < n) {
            while (j < n && a[j] == ' ') {
                j++; // skip spaces  
            }
            while (j < n && a[j] != ' ') {
                a[i++] = a[j++]; // copy non-spaces
            }
            while (j < n && a[j] == ' ') {
                j++; // skip spaces
            }
            if (j < n) {
                a[i++] = ' '; // append only one space
            }
        }

        return Arrays.copyOf(a, i);
    }

    // reverse a[] from a[i] to a[j]
    private void reverse(char[] a, int i, int j) {
        while (i < j) {
            char t = a[i];
            a[i++] = a[j];
            a[j--] = t;
        }
    }
}

Multi-reverse + Two Pointers - O(n) time, O(1) space (7ms)

https://leetcode.com/problems/reverse-words-in-a-string/discuss/47720/Clean-Java-two-pointers-solution-(no-trim(-)-no-split(-)-no-StringBuilder\

public class Solution {
    public String reverseWords(String s) {
        if (s == null) return null;

        char[] a = s.toCharArray();
        int n = a.length;

        // step 1. reverse the whole string
        reverse(a, 0, n - 1);
        // step 2. reverse each word
        reverseWords(a, n);
        // step 3. clean up spaces
        return cleanSpaces(a, n);
    }

    void reverseWords(char[] a, int n) {
        int i = 0, j = 0;
        while (i < n) {
            while (i < n && a[i] == ' ') {
                i++; // skip spaces
            }
            // i is now the first index in the non-space word

            // update right pointer
            j = i;
            while (j < n && a[j] != ' ') {
                j++; // skip non-spaces
            }
            // j is now the first space on the right of a word

            // reverse the word we just found
            reverse(a, i, j - 1);

            // update left pointer
            i = j;
        }
    }

    // trim leading, trailing and multiple spaces
    String cleanSpaces(char[] a, int n) {
        int i = 0, j = 0;

        while (j < n) {
            while (j < n && a[j] == ' ') j++;             // skip spaces
            while (j < n && a[j] != ' ') a[i++] = a[j++]; // keep non spaces
            while (j < n && a[j] == ' ') j++;             // skip spaces
            if (j < n) a[i++] = ' ';                      // keep only one space
        }

        return new String(a).substring(0, i);
    }

    // reverse a[] from a[i] to a[j]
    private void reverse(char[] a, int i, int j) {
        while (i < j) {
            char t = a[i];
            a[i++] = a[j];
            a[j--] = t;
        }
    }
}

Using String operations trim(), split()- (65ms AC)

https://leetcode.com/problems/reverse-words-in-a-string/discuss/47706/My-accepted-Java-solution

public class Solution {
    public String reverseWords(String s) {
        String[] parts = s.trim().split("\\s+");
        String out = "";
        for (int i = parts.length - 1; i > 0; i--) {
            out += parts[i] + " ";
        }
        return out + parts[0];
    }
}