TCM TCM - 6 months ago 36
Java Question

Removing duplicate character from array

While reading one book named

Cracking the coding interview
by
Gayle Laakmann
, i came across this question


Design an algorithm and write code to remove the duplicate characters
in a string without using any additional buffer. NOTE: One or two
additional variables are fine. An extra copy of the array is not.


and this code :-

public static void removeDuplicates(char[] str) {
if (str == null) {
return;
}
int len = str.length;
if (len < 2) {
return;
}

int tail = 1;

for (int i = 1; i < len; ++i) {
int j;
for (j = 0; j < tail; ++j) {
if (str[i] == str[j]) {
break;
}
}
if (j == tail) {
str[tail] = str[i];
++tail;
}
}
str[tail] = 0;
}


which is supposed to remove duplicate character from the array. I don't quiet seem to understand what the algorithm is doing by replacing the same character again and again. I thought it's only me who feels that the algorithm is not working but infact when i ran this code it's giving me wrong outputs. Is this serious error in book or have i not understood the question?

YoK YoK
Answer

Algo seems to be working but not clearing leftover characters. Changed code to following and it works: Note: Replaced:

str[tail] = 0;

with :

    for(; tail < len;tail++){
        str[tail] = 0;
    }

public static void removeDuplicates(char[] str) {
        if (str == null) {
            return;
        }
        int len = str.length;
        if (len < 2) {
            return;
        }

        int tail = 1;

        for (int i = 1; i < len; ++i) {
            int j;
            for (j = 0; j < tail; ++j) {
                if (str[i] == str[j]) {
                    break;
                }
            }

            if (j == tail) {
                str[tail] = str[i];
                ++tail;
            }

        }
        for(; tail < len;tail++){
            str[tail] = 0;
        }

    }
Comments