Reverse words of a char[]/sentence in place

Question

I want to reverse the words of a string in place using constant space. The catch is that the words cannot contain consecutive whitespaces. I want to reduce all consecutive whitespaces between words to one whitespace and also ignore leading and trailing whitespaces. I was able to implement the in place reversal of words, but I'm struggling to implement removing the consecutive whitespaces between words and leading and trailing whitespaces. Can someone help me?

Here is what I have so far:

public char[] reverseWords(char[] s) {

    if (s == null)
        return null;

    int right = 0;


    s = reverseString(s, 0, s.length - 1);// get the reversed sentence
    //System.out.println(s);
    for (int left = 0; left < s.length; left++) {

        if (s[left] != ' ') {// for first word

            for (right = left; right < s.length && s[right] != ' '; right++)
                ; // get end of word

            s = reverseString(s, left, right - 1);
            left =(right - 1);// move left index to end of
                                                // word

            // s[left++] = ' ';
        }

    }
    return s;
}

public char[] reverseString(char[] strChars, int start, int end) {

    if (strChars == null)
        return null;

    while (start < end) {

        char temp = strChars[start];
        strChars[start] = strChars[end];
        strChars[end] = temp;

        start++;
        end--;
    }
    return strChars;
}

Answer 1

There is going to be easier/faster ways. I am just giving a thought which should be good in learning purpose.

First, do whatever you have now, which reverse words, and leave those consecutive space untouched.

then write another method to do consecutive space removing.

have 2 pointer, start at the first position where it is not space.

A and B keep on moving on together.

if (A != B), then we do s[A] = s[B]; s[B] = ' ';

If s[A] and s[A-1] is space, then A stop (A is now at the 2nd space), and only B continue moving forward. By such way, A stay the same position and will continue to copy from B, until B gives a non-space character.

and it ends when B hit the end.

in psuedo code, it is something like

int a = first position of non-space;
int b = a;

while b < s.size() {
  if (a != b) {
    s[a] = s[b]
    s[b] = ' '
  }
  if (both s[a] and s[a-1] are space)  { 
    increment b;
    // leave a untouched
  } else {
    increment a;
    increment b;
  }
}

Constant space, O(n) time

---

Another way, which can handle the removal of consecutive space in place when reversing words:

The hint is, include those extra spaces when doing reverse.

e.g. Given a string

abc    def     ghi
L                 (left)    

first reverse is trivial so I am skipping it. The hint is, for second word, you are going to stop the L at the position right after the first space:

cba    def     ghi
    L

the "right" side of the reverse is going to be the first right boundary of word:

cba    def     ghi
    L    R

Then do the reverse in place

cba fed        ghi
    L    R

Then keep on finding the next position of L to start reverse again:

cba fed        ghi
        L

Take similar logic

cba fed        ghi
        L        R

then

cba fed ihg       
        L        R

Answer 2

A very, very simple one-line solution would be to use REGEX (short for REGular EXpression). I have two ways of doing this and I'm using the String#replaceAll() and String#trim() method for this. So, here goes:

String line = "    Hello     World!  ";
line = line.replaceAll(" +", " "); // '+' = 1 or more i.e. at least 1.
// Hence it replaces ALL white spaces with a single space.
line = line.trim(); //This 'trims' the String to remove all leading and trailing 
// whitespaces.
System.out.println(line); //Output: "Hello World!"

A more accepted practice is to use "\\s+" instead of " ". (Actually the character is \s but double slashes should be used when storing in a String.) You'll still get the same result. You could also try using the Pattern-Matcher approach.