Check if a String can become Empty by Recursively Deleting a Given Sub-String in Java
Given are the strings "str" and "sub_str". We may remove "sub_str" from "str" as often as we like. The fact that "sub_str" only appears once at a time is also assumed. The aim is to repeatedly remove "sub_str" to see if "str" may become empty.
Example 1:
Input:
String = “FIRFIRSTST”
Sub_String = “FIRST”
Output:
Yes, the given String can become Empty.
Explanation:
The substring "FIRST" at position 4 of the string "FIRFIRSTST" can first be removed. The modified string is now "FIRST". Again, the substring "FIRST" can be removed from position 1. The string is now empty.
Example 2:
Input:
String = “ICKQUICKQU”
Sub_String = “QUICK”
Output:
No, the given String cannot become Empty.
Explanation:
There is no possible method to empty the string in any way.
Approach: Using Inbuilt String Functions
Using the built-in string operations find() and erase() is an easy way of dealing with the problem. Using find(), which returns the initial index of the sub-string in the string that was initially entered or -1 if not found, the original text is iterated to get the index of the sub-string. The sub-string is then deleted using erase() until the original string's length is greater than 0. To begin, enter the sub-string substr for use in the main string str. The provided substring only appears once, which explains why the above technique is simple and easy to work.
Implementation:
FileName: StringEmpty.java
import java.io.*;
import java.util.*;
public class StringEmpty
{
// Returns true if sub_str can be removed
// recursively from str to make it empty.
static boolean Empty(String str, String sub_string)
{
while (str.length() > 0)
{
// index: To store the first index of any substring
// that was found in the main string
int index = str.indexOf(sub_string);
if (index == -1)
{
break;
}
// deleting the identified sub-string from the original string
str = str.replaceFirst(sub_string,"");
}
return (str.length() == 0);
}
public static void main(String[] args)
{
String str = "QUQUITEITE";
String sub_string = "QUITE";
if (Empty(str, sub_string))
{
System.out.print("\nYes, the given String can become Empty.");
}
else
{
System.out.print("\nNo, the given String cannot become Empty.");
}
}
}
Output:
Yes, the given String can become Empty.
Complexity Analysis:
The time complexity of the above approach is O(N^2), and the space complexity is given by O(N+M), where N represents the length of the original string, and M represents the length of the Substring.
Approach: By Using the Regular Expressions
The regular expression could be used as an alternate approach. With strings, regular expressions modules are highly useful. The search function in the regular expression module is used to look for patterns in the string. The replace function can be used to replace the characters in a string.
Algorithm:
Step -1: To identify a pattern in a string, use the re. The search function on the string.
Step -2: To replace a string part, use the re. Replace function.
Step -3: Repeat processes of one and two until a sub-string appears in the string as a result of the replacement.
Step -4: After all replacement, the string can finally become empty if it is empty; otherwise, it cannot.
Implementation:
Filename: StringEmpty1.java
import java.io.*;
import java. util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class StringEmpty1
{
// Returns true if sub_str can be removed
// recursively from str to make it empty.
static boolean Empty(String str, String sub_string)
{
Pattern t = Pattern.compile(sub_string);
Matcher x;
while((x = t.matcher(str)).find())
{
// Using replaceAll(), " replaces the match.
str = x.replaceAll("");
}
return str.equals("");
}
public static void main(String[] args)
{
String str = "WOWORLDRLD";
String sub_string = "WORLD";
if (Empty(str, sub_string))
{
System.out.println("\nYes, the given String can become Empty.");
}
else
{
System.out.println("\nNo, the given String can become Empty.");
}
}
}
Output:
Yes, the given String can become Empty.
Complexity Analysis:
The above approach also has similar complexities, i.e., O(N^2) for time and space complexity; it is O(N+M).