Reverse Words in a String | Leetcode

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.

click to show clarification.

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: Reverse the entire string. Then reverse each word. This means that we should refactor reverseChars() into its own method since we will use it a few times.

Remove all extra spaces. We could have done this when we reverse each word, but the code will be much simpler if we do this step separately.

It is better to do this in-place (update the same character array instead of creating a new array or StringBuilder) as that would require less memory. With a quick search online, I found that most solutions are not in-place and hence arguably are not optimal solutions for this problem.

public class Solution {
    public String reverseWords(String s) {
        if (s.length() == 0) return s;
        
        char[] a = s.toCharArray();
        
        // Reverse the entire string.
        reverseChars(a, 0, a.length - 1);

        // Reverse each word in place.
        int wordStart = -1;
        
        for (int i = 0; i < a.length; i++) {
            if (wordStart >= 0) {
                if (a[i] == ' ') {
                    reverseChars(a, wordStart, i - 1);
                    wordStart = -1;
                }
            } else {
                if (a[i] != ' ') {
                    wordStart = i;
                }
            }
        }

        // Remember to reverse the last word as we will not
        // hit a space at the end of it.
        if (wordStart >= 0) {
            reverseChars(a, wordStart, a.length - 1);
        }
        
        // Trim string and between words.
        int stringIndex = 0;
        boolean hasSpace = false;
        
        for (int i = 0; i < a.length; i++) {
            if (a[i] != ' ') {
                if (hasSpace) {
                    a[stringIndex++] = ' ';
                    hasSpace = false;
                }
                a[stringIndex++] = a[i];
            } else {
                if (stringIndex > 0) {
                    hasSpace = true;
                }
            }
        }
        
        return new String(a, 0, stringIndex);
    }
    
    private static void reverseChars(char[] a, int startInclusive, int endInclusive) {
        for (int i = startInclusive, j = endInclusive; i < j; i++, j--) {
            char c = a[i];
            a[i] = a[j];
            a[j] = c;
        }
    }
}