[1047] Remove All Adjacent Duplicates In String

暴力法超過時間了XDDDDD

偷看一下答案原來要用stack QQ

char * removeDuplicates(char * s){

int len = strlen(s);

for (int i=0;i<len-1; i++)

{

if (s[i]==s[i+1])

{

for (int j=i;j<len-2;j++)

s[j]=s[j+2];

s[len-2]='\0';

return removeDuplicates(s);

}

}

return s;

}

那只好附一個stack  的版本

char * removeDuplicates(char * s){

int len = strlen(s);

int top = -1;

char* ret=calloc(len, sizeof(char));

for (int i=0;i<len; i++)

{

if (top< 0)//insert head

{

ret[++top]=s[i];

continue;

}

if (s[i]!=ret[top])//push

ret[++top]=s[i];

else //pop

ret[top--]='\0';

}

return ret;

}

然後因為insert head 的部分和一般push 其實做的事情是一樣的，可以再合併；但是也沒有變快就是了XD

......

char * removeDuplicates(char * s){

int len = strlen(s);

int top = -1;

char* ret=calloc(len, sizeof(char));

for (int i=0;i<len; i++)

{

if (top <0 || s[i]!=ret[top])//insert head or //push

ret[++top]=s[i];

else //pop

ret[top--]='\0';

}

return ret;

}