/* Ch1_3
Design an algorithm and
write code to remove the duplicate characters in a string with O(1) additional
buffer. */
/* This seemingly simple question turns out to be interesting. And I found the solution provided in the book is not quite right.
With the constraint of constant additional buffer, the solution has a O(n^2) running complexity. */
With the constraint of constant additional buffer, the solution has a O(n^2) running complexity. */
/* The implementation in C++ is slightly different than in java.
That’s because C-style string in C/C++ is NUL terminated using special
character ‘\0’, while in java a char array is not NUL terminated, and even ‘\0’
count as a char. Below is my implementation in both C++ and in java. */
/* c++ implementation */
void removeDuplicateNoBuffer(char * str) {
if (!str) {
return;
}
size_t size = strlen(str);
if (size < 2) {
return;
}
int current = 1;
while (str[current]
!= '\0') {
int i;
for (i = 0; i <
current; ++i) {
if (str[i] ==
str[current]) {
break;
}
}
if (i ==
current) {
++current;
} else {
i = current+1;
while (str[i] != '\0') {
str[i-1] = str[i];
++i;
}
str[i-1] = str[i];
}
}
}
/* java implementation */
public static void removeDuplicates(char [] str) {
if (str == null) {
return;
}
int len = str.length;
if (len < 2) {
return;
}
int current = 1;
while (current < len) {
int j;
for (j = 0; j < current; ++j) {
if (str[current] == str[j]) {
break;
}
}
if (j == current) {
++current;
}
else {
for (j = current+1; j < len-1; ++j) {
str[j-1]
= str[j];
}
len--;
str[len]
= 0;
}
}
}
No comments:
Post a Comment