How to delete duplicates in a string using recursion?

user_8267674 0
Viewed 669

I'm working on a function that uses recursion in order to delete duplicate characters in a string. Problem is, I'm not sure how to keep passing a string along in order to keep comparing adjacent characters without cutting the string somehow. Here's what I have so far:

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

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

As an example, stringClean("yyzzza") should return "yza". Any tips on how I should proceed?

recursion c++ string
2 Answers

C++

Here's what I just thought about

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

For one line recursion lovers:

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

Algorithm:

  • Start from the leftmost character and remove duplicates at the left corner if there are any.

  • If the length of the string is zero or one then return the string.

  • Check the leftmost character in the starting substring. If it is present then

    • Recur for a string of length n-1 (string without last character).

  • If the leftmost character is not present in the starting substring, then

    • Recur for the remaining string and store the unique character.

Implementation:

#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;
}
user_127737380
Related