Tuesday, December 4, 2012

Reverse Words In A Char Array - Java

I'm back again with a Java post in my blog :-)

Recently I came across an interview question - "Given a statement in char[], reverse the order of words in that statement without using any extra temporary char[] or String functions". Here is my solution for this question.

There will be N - 1 Runs for reversing a statement which has N words in it.

1st Run will move the First word in statement to make it as Last Word and move the remaining space from first position before the word just moved.

2nd Run will move the now First word in statement to make it as 2nd last word and the remaining space from first position before the word just moved.

So, (N-1)th Run will move the now First word in statement to make it as Nth last word (i.e., Second Word) and the space before it from first position. 

public class ReverseStatement {


private static final char WORD_DELIMITER = ' ';

public static void main(String[] args) {
char[] input = "One Two Three Four".toCharArray();
System.out.println(input);
new ReverseStatement().reverse(input);
System.out.println(input);
}

int wordsLength[];

public synchronized void reverse(char[] input) {

if (input == null) {
throw new NullPointerException("input");
}

if (input.length == 0) {
throw new IllegalArgumentException("input is empty");
}

if (input[0] == WORD_DELIMITER || input[input.length - 1] == WORD_DELIMITER) {
throw new IllegalArgumentException(
"input must not start or end with SPACE");
}

countAndUpdateWordsLength(input);

int newPosition = input.length;
for (int run = 1; run < (wordsLength.length); run++) {
newPosition = newPosition - wordsLength[run - 1];
shiftFirstNCharsTo(input, wordsLength[run - 1], newPosition);
shiftFirstNCharsTo(input, 1, --newPosition);
}
}

private void countAndUpdateWordsLength(final char[] input) {
int wordCount = 0;

// Loop to identify the total number of words.
int lastSpaceAt = 0;
for (int i = 0; i < input.length; i++) {

if (input[i] == WORD_DELIMITER) {
wordCount++;
if (lastSpaceAt == i)) {
throw new IllegalArgumentException(
"Continuous Spaces Detected " + i + ", " + lastSpaceAt);
}
lastSpaceAt = i;
}
}

// Incrementing by 1 for last word in input
wordCount++;

wordsLength = new int[wordCount];
int wordNumber = 0;
int eachWordLength = 0;

// Loop to count each word's length
for (int i = 0; i < input.length; i++) {
if (input[i] == WORD_DELIMITER) {
wordsLength[wordNumber] = eachWordLength;
eachWordLength = 0;
wordNumber++;
continue;
}
eachWordLength++;
}
wordsLength[wordNumber] = eachWordLength; // For the last word
}

private static void shiftFirstNCharsTo(char[] input, int n, int newPosition) {
if (newPosition + n > input.length) {
throw new RuntimeException("Cannot move to " + newPosition);
}
for (int x = n - 1; x >= 0; x--) {
int targetPosition = newPosition + n - 1;
for (int y = x; y < targetPosition; y++) {
char t = input[y];
input[y] = input[y + 1];
input[y + 1] = t;
}
newPosition--;
}
}
}

Output:
One Two Three Four
Four Three Two One

If you find any bug or improvement area, please comment.

5 comments:

  1. Hi,

    I have also similar query,

    We have a character array such as follows char –(a, ,c,a,t, ,f,a,l,l,s, ,d,o,w,n, ,a,n,d, ,m,e,o,w,s}

    Can you please provide me with an “In-place” algorithm to efficiently reverse this character array. By “In-Place” I mean a solution which will not create any extra resources e.g. by creating a second character array.

    So the required output would be {m,e,o,w,s, ,a,n,d, ,d,o,w,n, ,f,a,l,l,s, ,c,a,t, ,a}


    I have tried many, but i could able to achieve it.

    ReplyDelete
    Replies
    1. My solution above should work for you. But, It had a bug handling the "A" (single character word) in the beginning. I have fixed it. It should work now.

      Delete
    2. Hi Kajan,

      Thank you for coming back,

      In your case you take I/P as a String and converting this into Char Array. how about the taking char[] test = {a, ,c,a,t, ,f,a,l,l,s, ,d,o,w,n, ,a,n,d, ,m,e,o,w,s}; as a I/P value and get the O/P as {m,e,o,w,s, ,a,n,d, ,d,o,w,n, ,f,a,l,l,s, ,c,a,t, ,a}.

      Please help me.

      Vinoth

      Delete
    3. I just used a String to simplify creating char[]; to save some keystrokes. You can pass any char[] to my method for reversing the words in-place.

      Delete
    4. Yes, it worked! thank you very much and much appreciated and you have saved my day.

      Delete