Dada una string «str» y otra string «sub_str». Se nos permite eliminar «sub_str» de «str» cualquier número de veces. También se da que el “sub_str” aparece solo una vez a la vez. La tarea es encontrar si «str» puede quedar vacío eliminando «sub_str» una y otra vez.
Ejemplos:
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.
Método n.º 1: una solución simple para resolver este problema es utilizar las funciones de string incorporadas find() y erase(). Primero ingrese la substring substr para fines de búsqueda en la string original str, luego itere la string original para encontrar el índice de la substring usando find() que devuelve el índice inicial de la substring en la string original sino -1 si not found y borre esa substring usando erase() hasta que la longitud de la string original sea mayor que 0.
Las soluciones simples anteriores funcionan porque la substring dada aparece solo una vez a la vez.
C++
// C++ Program to check if a string can be
// converted to an empty string by deleting
// given sub-string from any position, any
// number of times.
#include<bits/stdc++.h>
using namespace std;
// Returns true if str can be made empty by
// recursively removing sub_str.
bool canBecomeEmpty(string str, string sub_str)
{
while (str.size() > 0)
{
// idx: to store starting index of sub-
// string found in the original string
int idx = str.find(sub_str);
if (idx == -1)
break;
// Erasing the found sub-string from
// the original string
str.erase(idx, sub_str.size());
}
return (str.size() == 0);
}
// Driver code
int main()
{
string str = "GEEGEEKSKS", sub_str = "GEEKS";
if (canBecomeEmpty(str, sub_str))
cout<<"\nYes";
else
cout<<"\nNo";
return 0;
}
Java
//Java program to check if a string can be
// converted to an empty string by deleting
// given sub-string from any position, any
// number of times.
class GFG {
// Returns true if str can be made empty by
// recursively removing sub_str.
static boolean canBecomeEmpty(String str, String sub_str) {
while (str.length() > 0) {
// idx: to store starting index of sub-
// string found in the original string
int idx = str.indexOf(sub_str);
if (idx == -1) {
break;
}
// Erasing the found sub-string from
// the original string
str = str.replaceFirst(sub_str,"");
}
return (str.length() == 0);
}
// Driver code
public static void main(String[] args) {
String str = "GEEGEEKSKS", sub_str = "GEEKS";
if (canBecomeEmpty(str, sub_str)) {
System.out.print("\nYes");
} else {
System.out.print("\nNo");
}
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to check if a string can be
# converted to an empty string by deleting
# given sub-string from any position, any
# number of times.
# Returns true if str can be made empty by
# recursively removing sub_str.
def canBecomeEmpty(string, sub_str):
while len(string) > 0:
# idx: to store starting index of sub-
# string found in the original string
idx = string.find(sub_str)
if idx == -1:
break
# Erasing the found sub-string from
# the original string
string = string.replace(sub_str, "", 1)
return (len(string) == 0)
# Driver code
if __name__ == "__main__":
string = "GEEGEEKSKS"
sub_str = "GEEKS"
if canBecomeEmpty(string, sub_str):
print("Yes")
else:
print("No")
# This code is contributed by
# sanjeev2552
C#
// C# program to check if a string can be
// converted to an empty string by deleting
// given sub-string from any position, any
// number of times.
using System;
class GFG
{
// Returns true if str can be made empty by
// recursively removing sub_str.
static Boolean canBecomeEmpty(String str, String sub_str)
{
while (str.Length > 0)
{
// idx: to store starting index of sub-
// string found in the original string
int idx = str.IndexOf(sub_str);
if (idx == -1)
{
break;
}
// Erasing the found sub-string from
// the original string
str = str.Replace(sub_str,"");
}
return (str.Length == 0);
}
// Driver code
public static void Main(String[] args)
{
String str = "GEEGEEKSKS", sub_str = "GEEKS";
if (canBecomeEmpty(str, sub_str))
{
Console.Write("\nYes");
}
else
{
Console.Write("\nNo");
}
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to check if a string can be
// converted to an empty string by deleting
// given sub-string from any position, any
// number of times.
// Returns true if str can be made empty by
// recursively removing sub_str
function canBecomeEmpty(str,sub_str)
{
while (str.length > 0)
{
// idx: to store starting index of sub-
// string found in the original string
let idx = str.indexOf(sub_str);
if (idx == -1) {
break;
}
// Erasing the found sub-string from
// the original string
str = str.replace(sub_str,"");
}
return (str.length == 0);
}
// Driver code
let str = "GEEGEEKSKS", sub_str = "GEEKS";
if (canBecomeEmpty(str, sub_str)) {
document.write("<br>Yes");
} else {
document.write("<br>No");
}
// This code is contributed by rag2127
</script>
Producción
Yes
Método n.º 2: una posible solución sería utilizar la expresión regular . El módulo de expresiones regulares es muy útil con strings. El módulo de expresiones regulares tiene una función de búsqueda que se usa para encontrar los patrones en una string. Y la función de reemplazo se usa para reemplazar los caracteres de la string. Los siguientes son pasos para nuestro enfoque:
- Use la función re.search en la string para encontrar el patrón en la string.
- Use la función re.replace para reemplazar la substring de la string.
- Repita los pasos uno y dos hasta que haya una substring en la string después de reemplazarla.
- Por último, si la string está vacía después de todos los reemplazos, entonces puede quedar vacía; de lo contrario, no puede quedar vacía.
C++
// C++ Program to check if a string can be
// converted to an empty string by deleting
// given sub-string from any position, any
// number of times.
#include<bits/stdc++.h>
using namespace std;
// Returns true if str can be made empty by
// recursively removing sub_str.
bool canBecomeEmpty(string str1 , string sub_str){
regex r(sub_str);
smatch m ;
// matches words beginning by "Geek"
while(regex_search(str1, m, r)){
// regex_replace() for replacing the match with 'geek'
str1 = regex_replace(str1, r, "");
}
// Returning result
return true ? str1=="" : false ;
}
// Driver code
int main()
{
string s = "GeeksForGeeGeeksks";
string k = "Geeks";
if (canBecomeEmpty(s, k)){
cout << "\nYes" ;
}
else {
cout << "\nNo";
}
return 0;
}
Python3
# Python3 program to check if a string can be
# converted to an empty string by deleting
# given sub-string from any position, any
# number of times.
# Returns true if str can be made empty by
# recursively removing sub_str.
import re
def canBecomeEmpty(string, sub_str):
# finding sub-string in string
while sub_str in string :
# Replacing sub-string from string
string = re.sub(sub_str, "", string)
# Returning result
return True if string == "" else False
# Driver code
if __name__ == "__main__":
string = "GeeksforGeeGeeksks"
sub_str = "Geeks"
if canBecomeEmpty(string, sub_str):
print("Yes")
else:
print("No")
# This code is contributed by
# sanjeev2552
Javascript
// Javascript program to check if a string can be
// converted to an empty string by deleting
// given sub-string from any position, any
// number of times.
// Returns true if str can be made empty by
// recursively removing sub_str
function canBecomeEmpty(str,sub_str)
{
// Regular expression for sub_string
const regex = new RegExp(sub_str);
// Iterating over string untill it matches sub_string
while(regex.test(str)){
// Replacing sub-string from string
str = str.replace(regex, '')
}
// Returning result
return false ? str : true ;
}
// Driver code
let str = "GeeksForGeeGeeksks", sub_str = "Geeks";
if (canBecomeEmpty(str, sub_str)) {
console.log("Yes");
} else {
console.log("No");
}
// This code is contributed by sam snehil
Producción
No
Este artículo es una contribución de Himanshu Gupta . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA