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

Given a string “str” and another string “sub_str”. We are allowed to delete “sub_str” from “str” any number of times. The task is to find if “str” can become empty by removing “sub_str” again and again.

Examples:

Input : str = “GEEGEEKSKS”, sub_str = “GEEKS”
Output : Yes
Explanation : In the string GEEGEEKSKS, we can first
delete the substring GEEKS from position 4.
The new string now becomes GEEKS. We can
again delete sub-string GEEKS from position 1.
Now the string becomes empty.

Input : str = “GEEGEEKSSGEK”, sub_str = “GEEKS”
Output : No
Explanation : In the string it is not possible to make the
string empty in any possible manner.

using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

namespace ConsoleApplication1
{
    class Program
    {
        public static int flag = 0;
        public static void Main(string[] args)
        {
            string str = "KEEKEEKK";
            string subStr = "KEEK";
            RecursiveDeletion(str, subStr);
            if(flag == 0)
            {
                Console.WriteLine("No");
            }
        }

        public static void RecursiveDeletion(string str, string subStr)
        {
            if (str == null || str.Length == 0)
            {
                Console.WriteLine("Yes");
                flag = 1;
            }
            else
            {
                for (int i = 0; i <= str.Length - subStr.Length && flag == 0; i++)
                {
                    if (str.Substring(i, subStr.Length) == subStr)
                    {
                        RecursiveDeletion(str.Remove(i, subStr.Length), subStr);
                    }
                }
            }
        }
    }
}

Output
=======
Yes
Press any key to continue . . .
Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s