0

This is my second post on this same method. The description of the method is as follows:

"Reduces all sequences of 2 or more spaces to 1 space within the characters array. If any spaces are removed then the same number of Null character '\u0000' will fill the elements at the end of the array."

The parameter for the method is a char array. I've succeeded in counting the amount of duplicate spaces, however, I cannot for the life of me figure out how to shift values down while accounting for such duplicate spaces. At the end, the method is supposed to replace the number of indexes of duplicate spaces with '\u0000' characters. This is what I have so far:

// Calculate duplicate count before changing the array
    int duplicateCount = 0;
    for(int i = 0; i + 1 < characters.length; i++){
        if(characters[i] == ' ' && characters[i + 1] == ' '){
            duplicateCount++;
        }
    }

    // Shift the array down however much is needed
    for(int j = 0; j + 1 < characters.length; j++){
        if(characters[j] == ' ' && characters[j + 1] == ' '){
            for(int a = j, b = a + 1; b < characters.length; a++, b++){
                characters[a] = characters[b];
            }
        }
    }
    for(int replace = characters.length - duplicateCount; replace < characters.length; replace++){
        characters[replace] = '\u0000';
    }
}

Thus, if the input was:char [] characters = {'a', 't', ' ', '.', ' ', ' ', 'g', ' ', ' ', 'h', ' '};

The output should be: char [] expectedResult = {'a', 't', ' ', '.', ' ', 'g', ' ', 'h', ' ','\u0000', '\u0000'};

Thank you folks, this problem seems like it should be so simple yet I'm stuck. If you can offer any explanation to your answer, I'd very much appreciate it. Thank you again.

Improve this question
6
  • do you HAVE to do it in place? it seems much less efficient compared to simply making a single pass through the original array and copying over characters into a new array Commented Feb 23, 2016 at 16:43
  • I believe so, or at least make whatever the result is going to be to be under the "character" variable, if possible. So if I make a second array, the second array would essentially have to be copied back into the first. Would that be possible? Commented Feb 23, 2016 at 16:47
  • you can simply reassign the reference of the characters array to that of the new array, no copying necessary Commented Feb 23, 2016 at 16:49
  • Ah, I see. so basically what I'd have to do is put all characters from the first array into the new array, unless a space is repeated two or more times. So somehow I'll have to filter that out. And then at the end add those \u0000 characters for however many I need Commented Feb 23, 2016 at 16:52
  • yup, there should be a way you can do it with only a single pass of the first array. Commented Feb 23, 2016 at 16:53

4 Answers 4

Reset to default
2

It's easy enough to do it in place. Just iterate through the array keeping track of both the index you're checking (to see if it is an extra space) and the index you're copying to. In the end, fill the array out with your '\u0000' value and you're done.

I made it a simple state machine to make it easy to keep track of whether we're getting extra spaces or not.

public void squeezeMe(char[] characters) {
    SqueezeState state = SqueezeState.START;

    int p = 0;
    for (int i = 0; i < characters.length; i++) {
        SqueezeState newState = SqueezeState.START;

        // Evaluate input based on current state
        switch (state) {
        case START:
        case NOT_A_SPACE: {
            if (Character.isWhitespace(characters[i])) {
                newState = SqueezeState.FIRST_SPACE;
            } else {
                newState = SqueezeState.NOT_A_SPACE;
            }
            break;
        }
        case FIRST_SPACE:
        case EXTRA_SPACE: {
            if (Character.isWhitespace(characters[i])) {
                newState = SqueezeState.EXTRA_SPACE;
            } else {
                newState = SqueezeState.NOT_A_SPACE;
            }
        }
        }

        // Transition to new state
        switch (newState) {
        case NOT_A_SPACE:
        case FIRST_SPACE: {
            if (i > p) {
            characters[p] = characters[i];
            }
            p++;
            break;
        }
        }

        state = newState;
    }

    for (int i = p; i < characters.length; i++) {
        characters[i] = '\u0000';
    }

}

private enum SqueezeState {
    START, NOT_A_SPACE, FIRST_SPACE, EXTRA_SPACE;
}

@Test
public void test1() {
    char[] result = { 'a', 't', ' ', '.', ' ', ' ', 'g', ' ', ' ', 'h', ' ' };
    char[] expected = { 'a', 't', ' ', '.', ' ', 'g', ' ', 'h', ' ', '\u0000', '\u0000' };
    squeezeMe(result);
    assertEquals(expected.length, result.length);
    for (int i = 0; i < expected.length; i++) {
        assertEquals("Index " + i, expected[i], result[i]);
    }
}

If you'd rather not use the state machine, you could do it like this:

public void squeezeMe(char[] characters) {
    boolean copyThis = false;
    boolean wasLastASpace = false;

    int p = 0;
    for (int i = 0; i < characters.length; i++) {
        if (Character.isWhitespace(characters[i])) {
            copyThis = !wasLastASpace;
            wasLastASpace = true;
        } else {
            copyThis = true;
            wasLastASpace = false;
        }

        if (copyThis) {
            if (i != p) {
                characters[p] = characters[i];
            }
            p++;
        }
    }

    for (int i = p; i < characters.length; i++) {
        characters[i] = '\u0000';
    }
}
Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Is there any way to do this without the state machine? I'm afraid I'm unsure of how it works and haven't yet learned it.
Thank you very much for this, you wouldn't believe how helpful it is. I'm slowly starting to understand how it works. Did you develop any sort of algorithm that you'd care to share? If not that's ok.
It isn't much of an algorithm. It just takes advantage of the fact that you are removing from the original array, never adding. So if a character starts at position n, its ending position will always be no greater than n. That makes it safe and easy to read from and copy to the same array. After that it's just a matter of copying the characters you want to keep and ignoring the rest.
Interesting. I'm slowly working through the code and understanding it more and more.
1

You can copy it in a single pass through the array, using two integer pointers for "input" and "output", as indexes into the input and output arrays respectively.

char[] output = new char[input.length];
output[0] = input[0];  // Copy the first character, it's not a repeated space.
int ip = 1;
int op = 1;
while (ip < input.length) {
  if (input[ip] != ' ' || input[ip - 1] != ' ') {
    output[op++] = input[ip++];
  } else {
    ip++;
  }
}
while (op < output.length) {
  output[op++] = '\0';
}
Improve this answer

1 Comment

This seems to work although the output is left with three '\u000' characters instead of the expected 2. I'm looking into why that is.
0

I'm guessing this is your homework and you are not supposed to use any libraries and such. Here is my solution using a regular expression.

import java.util.Arrays;
import java.util.regex.Pattern;
public class ReplaceMultipleWhiteSpace(){
public static void main(String[] args){
    char[] array = new char[]{'a', ' ', ' ', ' ', ' ', ' ', 'b', ' ', 'c'};
    String s = new String(array);
    int length = s.length();
    Pattern twoOrMoreWhiteSpace = Pattern.compile("( {2,})");
    String replaced = twoOrMoreWhiteSpace.matcher(s).replaceAll(" ");
    int diff = length - replaced.length();
    char[] charArray = replaced.toCharArray();
    char[] finalArray = Arrays.copyOf(charArray, replaced.length() + diff);
    for (int i = replaced.length(); i < finalArray.length; i++) {
        finalArray[i] = '\u0000';
    }
    System.out.println(Arrays.toString(array));
    System.out.println(Arrays.toString(finalArray));
}
}
Improve this answer

3 Comments

You're correct, it is homework. I asked if I could use any other methods and the answer was no. Thank you though, this is a helpful solution.
How are you accessing Pattern? Do you have to import it somehow?
Yes, it is in java.util.regex.Pattern; i edited the post to a full programm
0

The code below should be pretty obvious. You do not need to count the number of characters you need to fill at the end - just fill those that meet the criteria (=the previous and the current character are not both ' '), if it doesn't meet the criteria, don't copy it. At the end, just fill the remaining part of the array.

char[] result = new char[characters.length];

// copy the first character
result[0]=characters[0];
int resultIndex=1;

for(int i=1; i<characters.length; i++) {
    // if the current character and the last character are not both spaces
    if(!(result[resultIndex-1]==' ' && characters[i]==' ')) {
        result[resultIndex++]=characters[i];
    }
}

// fill the rest of the array with '\u0000'
while (resultIndex<characters.length) {
    result[resultIndex++]='\u0000';
}

return result;
Improve this answer

1 Comment

It seems that this returns the exact same array that we started with?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.