如何使用递归删除字符串中的重复元素？

Question

我正在编写一个使用递归的函数，以删除字符串中的重复字符。问题是，我不确定如何继续传递字符串以便比较相邻字符而不切割字符串。以下是我的代码：

string stringClean(const string& str)
{
   string s1 = str;

   if (/*first char == next char*/)
      s1.at(/*first char*/) = "";
      return stringClean(s1);
   else 
      return s1;
}

作为一个例子，stringClean（“yyzzza”）应该返回“yza”。你有什么建议我该怎么做？

- JURO312

---

重复项总是相邻的吗？ - David G

是的。其他预期结果的示例包括： - JURO312

stringClean("abbbcdd") → "abcd" stringClean("Hello") → "Helo" - JURO312

如果 (str [0] == str [1])，则返回 str [0] + stringClean（str.substr（2））; 否则返回 str [0] + stringClean（str.substr（1））; 终止条件留给读者作为练习。 - Igor Tandetnik

这个问题不适合使用递归解决。这是一道作业题吗？无论如何，你需要更具体地提出问题，而不是仅仅询问“有什么提示”。按照要求，实际上这个问题要求编写递归函数的教程。请阅读 https://stackoverflow.com/help/asking。特别注意第5条 - MCVE。然后发布一个展示更多努力的MCVE。 - Jive Dadson

Answer 1

C++

这是我刚想到的

#include <iostream>
#include <string>

std::string rec(std::string &word, int index);
std::string rec(std::string word) {
    if(word.length() <= 1) {
         return word;
    }
    return word[0] + rec(word, 1);
}

std::string rec(std::string &word, int index) {
   if(index == word.length()) {
       return "";
   }
   return (word[index] != word[index-1] ? std::string(1, word[index]) : "") + rec(word, index+1); 
}

int main() {
    std::cout << rec("aaabbbbcccddd") << std::endl;
}

对于单行递归爱好者：

std::string rec(std::string &word, int index) {
   return index == word.length() ? "" : (word[index] != word[index-1] ? std::string(1, word[index]) : "") + rec(word, index+1); 
}

- CMPS

---

如果你有abcdabcddcbadcba呢？ - user5550963

Answer 2

算法：

• 从最左边的字符开始，如果有重复的字符，则删除左侧角落的重复项。

• 如果字符串的长度为零或一，则返回该字符串。

• 检查起始子字符串中最左边的字符。如果存在，则

  • 对长度为n-1的字符串（不包括最后一个字符的字符串）进行递归。

• 如果起始子字符串中不存在最左边的字符，则

  • 对剩余的字符串进行递归，并存储唯一的字符。

实现：

#include <string>
#include <iostream>

using namespace std;

string removeDups(string s) {
    if(s.length() <= 1) return s;
    if(s.substr(0, s.length() - 1).find(s.substr(s.length() - 1, s.length())) != string::npos) {
        return removeDups(s.substr(0, s.length() - 1));
    } else {
        return removeDups(s.substr(0, s.length() - 1)) + s.substr(s.length() - 1, s.length());
    }
}


int main() {
    string s;
    cin >> s;
    cout << removeDups(s);
    
    return 0;
}

- Rudrakshi