Reverse string with identical spaces as in original String using Java

Question

This is interview question

Reverse string with identical spaces as in original String using Java

For example

Original String :

best in the world and is greatest and is making sure the world goes well

Output:

llew se ogd lrowe hte ru sgnikams idn at setaer gsid nad lrowe htni tseb

The code I have written is as below:

import java.util.ArrayList;
import java.util.List;

public class CountSpaces {
    public static void main(String[] args) {
        String st = "best in the world and is greatest and is making sure the world goes well";
        String st1 = st;
        char[] x = st.toCharArray();
        int flag = 0;
        List<Integer> spacePositionArray = new ArrayList<Integer>();
        int len = x.length;
        int sub = 0;
        for (int i = 1; i < len; i++) {
            char y = x[i];
            if (y == ' ') {
                if (flag > 0)
                    spacePositionArray.add(i - sub);
                else
                    spacePositionArray.add(i);
                flag++;
                sub++;
            }
        }

        st = st.replaceAll("\\s+", "");
        x = st.toCharArray();
        len = x.length;

        int k = 1;
        for (int i = len - 1; i >= 0; i--) {
            if (spacePositionArray.contains(k)) {
                System.out.print(x[i] + " ");
            }

            else
                System.out.print(x[i]);

            k++;
        }

        System.out.println();

        System.out.println(st1);
    }
}

Can it be done in a much simpler which is more logical. My approach is much more brute and direct.

Kindly review

Answer 1

You can make a String directly from a character array. So

public static String reverseWithoutMovingSpaces(String text) {
    char[] results = text.toCharArray();
    for (int left = 0, right = results.length - 1; left < right; left++, right++) {
        while (results[left] == ' ') {
            left++;

            if (left >= right) {
                return new String(results);
            }
        }

        while (results[right] == ' ') {
            right--;

            if (left >= right) {
                return new String(results);
            }
        }

        char temp = results[left];
        results[left] = results[right];
        results[right] = temp;
    }

    return new String(results);
}

Since we know the length of the intended string, we can manipulate the characters of the array directly. We don't need a List<Character> nor even a StringBuilder. We can just swap in place like this was C.

We also don't need to keep track of where the spaces are once we are past them.

This isn't a very Java solution, as it doesn't delegate to any of the library functions. But in this case, we would have to go to a lot of effort to make the problem delegate to library functions. It's just as easy to do the work directly.

Answer 2

I suggest you rely on StringBuilder. That way, appending to it runs in amortized constant time.

I had in mind the following implementation:

public static String reverseWithSpaces(String text) {
    StringBuilder stringBuilder = new StringBuilder(text.length());
    StringBuilder outputBuilder = new StringBuilder(text.length());
    String[] words = text.split("\\s+");
    
    for (String word : words) {
        stringBuilder.append(word);
    }
    
    stringBuilder.reverse();
    
    int index = 0;
    
    for (int i = 0; i < text.length(); ++i) {
        char c = text.charAt(i);
        
        if (c == ' ') {
            outputBuilder.append(' ');
        } else {
            outputBuilder.append(stringBuilder.charAt(index++));
        }
    }
    
    return outputBuilder.toString();
}

Above, you first lump all the non-whitespace characters to a single string builder stringBuilder. Then, you reverse the stringBuilder. The next step is to march over the input text, and for each position index you (1) add a space, or (2) add a character (in order) from the stringBuilder.

Answer 3

You don't need all that much to do this. Both the OP's solution and @coderodde's seem overworked with too many extraneous objects.

One StringBuilder is needed for the result. We also need an index into the char array from the original string, initially set to the length of the original string.

Loop over the chars in the array. If a char is space add it to the output otherwise decrement the index till you find a non-space and copy that. (I'd probably write a little method to search down the array for the next non-space, or even a class implementing Iterator, just to look clever 😉)

Done!

I don't have a development environment to hand, so I leave the actual implementation as an exercise for the reader...