Check if string can become empty by recursively deleting given sub-string

Check if the given input string can be deleted completely by deleting given input sub-string recursively.

Given sub-string should be present in the input string

Examples

a) Input string : cocodede
    sub-string : code
    Output : True

Here, delete code from this position co”code”de, then delete the remaining “code”  from the string, then string becomes empty.

b) Input string : cocoded
    sub-string : code
    Output : False

Here, delete code from this position co”code”d, then remaining word is cod. So, output False

Algorithm

Here we use STL functions find() and erase().

1. Traverse the input_string.

2. If find sub-string, store it.

3. Erase the sub-string, if sub-string not found return No

4. Else, if it reaches the end, return Yes.

C++ Program

#include <bits/stdc++.h>

using namespace std;
 
bool CanBeEmpty(string input_string, string sub_string)
{
    while (input_string.size() > 0)
    {
        //index is start index of found sub strinf
        int index = input_string.find(sub_string);
        if (index == -1)//If not found
        {
            break;
        }
        //Erase sub-string
        input_string.erase(index, sub_string.size());
    }
    //If final length of string is 0, return true
    if (input_string.size() == 0)
    {
        return true;
    }
    else
    {
        return false;
    }
}
 
//Main function
int main()
{
    string input_string = "cocodede", sub_string = "code";
    if (CanBeEmpty(input_string, sub_string))
    {
        cout<<"Yes";
    }
    else
    {
        cout<<"No";
    }
    return 0;
}
Try It

 


Next > < Prev
Scroll to Top