递归删除重复的字符

Question

我想写一个递归函数，它递归地从给定的字符串中删除所有重复的字符。 例如“Hello world” - >“Helo wrd”。

我有局限性是：

1. 没有循环不允许的。
2. 没有更多参数可以添加到原始函数（remove_duplicates）。
3. string.h库中没有函数允许，但我可以递归地写入它们。

我被允许使用另一个辅助递归函数。

到目前为止，我写的函数只适用于短字符串，它会多次调用该函数。任何建议如何使它更有效率？

void remove_duplicates3(char string[], int index)//(str,RecursiveStrlen(str, 0)-1) 
{ 
    int length = RecursiveStrlen(string + 1, 0); 
    if (string[index] == '\0' || index == 0) 
    { 
     return; 
    } 

    if (string[0] != string[index]) 
    { 
     remove_duplicates3(string, index - 1); 
    } 
    else 
    { 
     BackspaceString(string, index); 
     remove_duplicates3(string, length - 1); 
    } 

    remove_duplicates3(string + 1, length - 1); 
} 

int RecursiveStrlen(char str[], int index) 
{ 
    if (str[index] == '\0') 
     return index; 
    return RecursiveStrlen(str, index + 1); 
} 


void BackspaceString(char string[],int index)//deletes one char from string in a specific index 
{ 
    if (string[index] == '\0')//end of string 
     return; 
    string[index] = string[index + 1]; 
    BackspaceString(string, index + 1); 
} 

Answer 1

纯递归解决方案：

void remove_char(char string[], char c, int read_index, int write_index) { 
    if (string[read_index] == 0) { 
     string[write_index] = 0; 
     return; 
    } 
    if (c == string[read_index]) { 
     remove_char(string, c, read_index + 1, write_index); 
    } else { 
     string[write_index] = string[read_index]; 
     remove_char(string, c, read_index + 1, write_index + 1); 
    } 
} 

void remove_duplicates(char string[], int index) { 
    if (string[index] != 0 && string[index + 1] != 0) { 
     remove_char(string, string[index], index + 1, index + 1); 
     remove_duplicates(string, index + 1); 
    } 
} 

Answer 2

如果你可以使用全局变量来存储得到的线，你可以这样做：

char result[30]=""; 
char over[30]=""; 


int check(char *over, char c) 
{ 
    if(*over != '\0') 
    { 
     if(*over == c) 
     { 
      return 1; //exists 
     } 
     else 
     { 
      return check(over+1, c); 
     } 
    } 
    return 0; //doesn't exist 
} 

int strLen(char *str) 
{ 
    if(*str=='\0') 
    { 
     return 0; 
    } 
    return strLen(str+1)+1; 
} 

void remove_duplicates(char *str) 
{ 
    if(*str != '\0') 
    { 
     if(check(over, *str)==0) 
     { 
      int len=strLen(result); 
      result[len++]=*str; 
      result[len]='\0'; 

      len=strLen(over); 
      over[len++]=*str; 
      over[len]='\0'; 
     } 
     remove_duplicates(str+1); 
    } 
} 

得到的字符串存储在result和over是将存储已经遇到了一个字符串字符作为字符串。 over由check()函数对照字符c检查以返回0如果c未在over中找到。

check()检查over的值以确定其参数c是否存在于over中。

remove_duplicates()将检查输入字符串str中的每个字符。如果在str之前没有遇到该字符，则将其添加到已遇到的字符列表中over，并将其添加到result字符串中。

直到输入字符串str结束为止。

Answer 3

如果你的字符串只有ASCII字符 -

int arr[256] = {0}; 

/* 
* str - Input string 
* presult - Pointer to the buffer contain result 
*/ 
void remove_duplicates(char *str, char *presult) 
{ 
    if(*str != '\0') 
    { 
     if(arr[*str] == 0) 
     { 
      *presult = *str; 
      arr[*str] = 1; 
      remove_duplicates(str+1, presult+1); 
     } 
     remove_duplicates(str+1, presult); 
    } 
}