递归地在字符串中删除重复字符

Question

我正在尝试创建一个递归函数来从字符串中删除连续重复的字符。它可以正常工作，除了前几个字符。例如，如果我的输入是 MMMMMuuuuuOOOOOKKKKLLLEE OOOOLLL 或类似的内容，输出是 MMuOKLE OL。你可以看到，除了前两个 M 之外，其余部分都可以正常工作。如何使其对前面的部分也可以正常工作呢？以下是我的代码：

#include <stdio.h>

char* remove_duplicates (char* str){
    if(*(str+1)!='\0'){
        if(*str==*(str+1)){
            *(str+1)=*(str+2);
             remove_duplicates(str+1);
        }
        remove_duplicates(str+1);
    }
    return str;
}

int main()
{
    char sample[] = "MMMMMuuuuuOOOOOKKKKLLLEE OOOOLLL";

    printf("OLD: |%s|\n", sample);
    printf("NEW: |%s|\n", remove_duplicates(sample));

    return 0;
}

- gokbeykeskin

---

除了其他可能出现的问题，如果您将空字符串（""）传递给 remove_duplicates() 函数会发生什么？ - Steve Friedl

简化测试用例，只保留最小的字符串以便发现问题。然后在纸上和调试器中逐步分析它。 - kaylum

@SteveFriedl 我在主函数中传递了 "" 给 remove_duplicates()。什么也没有发生。它再次打印出菜单。 - gokbeykeskin

@gokbeykeskin - 我认为你需要更仔细地看待这个问题。如果第一个字符是NUL字节，后面的所有内容都是随机垃圾，那么会导致函数停止的原因是什么？ - Steve Friedl

为什么要返回参数而不是使用 void remove_duplicates(char * str)？这样做会使第二次调用毫无意义。 - bruno

@gokbeykeskin，你将无效代码的答案标记为最佳答案。 - Vlad from Moscow

Answer 1

我是这样做的：

#include <stdio.h>

char* remove_duplicates(char* str)
{
    if (*str)
    {
        char* dest = remove_duplicates(str + 1);
        str = (*str == *dest) ? dest : ((*(dest - 1) = *str), (dest - 1));
    }
    return str;
}

int main()
{
    char sample[] = "MMMMMuuuuuOOOOOKKKKLLLEE OOOOLLL";
    char sample2[] = "AA";

    printf("OLD: |%s|\n", sample);
    printf("NEW: |%s|\n", remove_duplicates(sample));

    printf("OLD: |%s|\n", sample2);
    printf("NEW: |%s|\n", remove_duplicates(sample2));

    return 0;
}

输出

OLD: |MMMMMuuuuuOOOOOKKKKLLLEE OOOOLLL|
NEW: |MuOKLE OL|
OLD: |AA|
NEW: |A|

- abelenky

---

有趣的是，它将非重复项移动到末尾，然后返回字符串中非重复项开始的指针，但原始字符串（例如，如果再次打印“sample”）仍包含重复项。 - David C. Rankin

@abelenky 您提供了错误的代码。请尝试以下代码 char sample[] = "AA"; remove_duplicates( sample ); printf( ""%s"\n", sample ); - Vlad from Moscow

@Vlad：我的代码确实会直接修改“sample”，但它会返回一个指向数组正确部分的指针。你可以尝试使用printf("\"%s\"\n", remove_duplicates(sample));，你会看到返回值是正确的。 - abelenky

@abelenky 这是一种无效的方法。您必须从函数作为参数传递的指针所指向的原始字符串中删除重复项。 - Vlad from Moscow

@Vlad 在问题描述中没有指定这一点。我的返回值是正确的。 - abelenky

Answer 2

在这里。

#include <stdio.h>

char * remove_duplicates( char *s )
{
    if ( *s )
    {
        if ( *s == *( s + 1 ) )
        {
            *( s + 1 ) = *( s + 2 );
            remove_duplicates( s + 1 );
            remove_duplicates( s );
        }
        else
        {
            remove_duplicates( s + 1 );
        }           
    }

    return s;
}

int main(void) 
{
    char s[] = "MMMMMuuuuuOOOOOKKKKLLLEE";

    remove_duplicates( s );

    puts( s );

    return 0;
}

程序输出是：

MuOKLE

- Vlad from Moscow

---

逻辑很痛苦 :) 但是所有具有多个递归调用的递归逻辑都是如此... 做得好。 - David C. Rankin

Answer 3

我这里只是添加了递归函数（语言：C++），而不是整个代码。

void removeConsecutiveDuplicates(char input[]) {
   
    if(input[0] == '\0' || input[1]=='\0') return;
    if(input[0]!=input[1]) return removeConsecutiveDuplicates(input+1);
    else
    {
        for(int i=1;i<=strlen(input);i++)
        {
            input[i-1] = input[i];
        }
       return removeConsecutiveDuplicates(input);
    }  
    return; 
}

- Hema Priya Velaga

---

你好，欢迎来到 Stack Overflow！请参观一下 导览。感谢您提供答案，但您能否添加一些解释说明您的代码是如何解决问题的呢？查看这个 帮助中心文章 以获取有关格式化代码的帮助。 - Jeanne Dark

Answer 4

感谢大家的帮助。如你们所说，我在纸上仔细检查了我的代码，发现问题出在它没有比较第一个和最后一个 M。

我添加了一个新的 if 语句 if(*str==*(str-1)) *(str)=*(str+1);，现在它可以正常工作了。

现在函数是：

char* remove_duplicates (char* str){
    if(*(str+1)!='\0'){
        if(*str==*(str+1)){
            *(str+1)=*(str+2);
            remove_duplicates(str+1);
        }
        remove_duplicates(str+1);
    }
    if(*str==*(str-1)) *(str)=*(str+1);
    return str;
}

- gokbeykeskin

Answer 5

递归太过复杂了，我认为。

让我们从字符串的开头开始使用两个指针。

首先，在字符串上进行循环。 当我们没有到达字符串末尾* p 时，向前查看p ++。

while (*p++) {
    if (*p == *current)
        continue;

如果下一个字符与当前字符相同，则继续查找下一个不同的字符。

current++;
*current = *p;

当发现不同的字符时，只需将其放在当前字符之后。

#include <stdio.h>

char* remove_duplicates (char* str){
    char *p = str;
    char *current = p;
    while (*p++) {
        if (*p == *current)
            continue;
        current++;
        *current = *p;
    }

    return str;
}

int main()
{
    char sample[] = "MMMMMuuuuuOOOOOKKKKLLLEE OOOOLLL";

    printf("OLD: |%s|\n", sample);
    printf("NEW: |%s|\n", remove_duplicates(sample));
    printf("NEW: |%s|\n", remove_duplicates(""));

    return 0;
}


OLD: |MMMMMuuuuuOOOOOKKKKLLLEE OOOOLLL|
NEW: |MuOKLE OL|
NEW: ||

使用AAAB来表示当前的详细信息

p
v
AAAB0
^
c

   p
   v
AAAB0
^
c

   p
   v
AAAB0
 ^
 c

   p
   v
ABAB0
 ^
 c

    p
    v
ABAB0
 ^
 c


    p
    v
ABAB0
  ^
  c


    p
    v
AB0B0
  ^
  c

我们得到了AB。

- Ôrel

---

太复杂了吗？我的函数只有4行代码，全部在一个if语句中，并且是递归的，正如所要求的那样。 - abelenky

@abelenky 请看David C. Rankin的评论，我认为该主题的递归并不简单，4行代码和一个大三元运算不确定是否简单。 - Ôrel