151. Reverse Words in a String

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

For example,
Given s = "the sky is blue",
return "blue is sky the".

Update (2015-02-12):
For C programmers: Try to solve it in-place in O(1) space.

Clarification:

• What constitutes a word?
  A sequence of non-space characters constitutes a word.
• Could the input string contain leading or trailing spaces?
  Yes. However, your reversed string should not contain leading or trailing spaces.
• How about multiple spaces between two words?
  Reduce them to a single space in the reversed string.

Solution:

Method 1: Use Java standard library

First split the string to a string array by " ".

Concatenate every non-empty string from the array with " " between each other.

Trim the last " ".



Code:

public class Solution {
    public String reverseWords(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }
        
        String[] str = s.split(" ");
        String res = "";
        for (int i = str.length - 1; i >= 0; i--) {
            if (str[i].length() > 0) {
                res += str[i] + " ";
            }
        }
        return res.trim();
    }
}

public class Solution {
    public String reverseWords(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }
        StringBuilder sb = new StringBuilder();
        String[] strs = s.split(" ");
        for (int i = strs.length - 1; i >= 0; i--) {
            if (strs[i].length() > 0) {
                sb.append(strs[i]);
                sb.append(" ");
            }
        }
        if (sb.length() > 0) {
            sb.deleteCharAt(sb.length() - 1);
        }
        return sb.toString();
    }
}

Method 2: in-place

1. reverse the entire input

2. reverse every word

3. clean up spaces

Space complexity O(1).



Code:

public class Solution {
    public String reverseWords(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }
        
        char[] arr = s.toCharArray();
        int n = arr.length;
        
        // reverse all
        reverse(arr, 0, n - 1);
        
        // reverse every word
        reverseWord(arr);
        
        // clean up spaces
        return clearSpace(arr);
    }
    
    public void reverse(char[] arr, int i, int j) {
        while (i < j) {
            char tmp = arr[i];
            arr[i++] = arr[j];
            arr[j--] = tmp;
        }
    }
    
    public void reverseWord(char[] arr) {
        int i = 0;
        int j = 0;
        int n = arr.length;
        
        while (i < n) {
            while (i < j || i < n && arr[i] == ' ') {
                i++;
            }
            while (j < i || j < n && arr[j] != ' ') {
                j++;
            }
            reverse(arr, i, j - 1);
        }
    }
    
    public String clearSpace(char[] arr) {
        int i = 0;
        int j = 0;
        int n = arr.length;
        
        while (j < n) {
            while (j < n && arr[j] == ' ') {
                j++;
            }
            while (j < n && arr[j] != ' ') {
                arr[i++] = arr[j++];
            }
            while (j < n && arr[j] == ' ') {
                j++;
            }
            if (j < n) {
                arr[i++] = ' ';
            }
        }
        
        return new String(arr).substring(0, i);
    }
}