遞歸刪除重複的字符

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); 
    } 
}