Corte de strings en Python para verificar si una string puede quedar vacía mediante la eliminación recursiva

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.

Tenemos una solución existente para este problema, consulte Verifique si una string puede quedar vacía al eliminar recursivamente un enlace de substring determinado. Resolveremos este problema en python usando String Slicing . El enfoque es muy simple,

1. Use el método find() de string para buscar una substring de patrón dada.
2. Si la substring se encuentra en la string principal, la función de búsqueda devolverá el índice de su primera aparición.
3. Ahora corte la string en dos partes, (i) desde el inicio de la string hasta el índice 1 de la substring fundada, (ii) (comience desde el primer índice de la substring fundada + longitud de la substring) hasta el final de la string.
4. Concatene estas dos partes cortadas y repita desde el paso 1 hasta que la string original quede vacía o ya no encontremos una substring.

Implementación:

def checkEmpty(input, pattern):
     
    # If both are empty
    if len(input)== 0 and len(pattern)== 0:
        return 'true'
 
    # If only pattern is empty
    if len(pattern)== 0:
        return 'true'
 
    while (len(input) != 0):
 
        # find sub-string in main string
        index = input.find(pattern)
 
        # check if sub-string founded or not
        if (index ==(-1)):
            return 'false'
 
        # slice input string in two parts and concatenate
        input = input[0:index] + input[index + len(pattern):]           
    return 'true'
 
# Driver program
if __name__ == "__main__":
    input ='GEEGEEKSKS'
    pattern ='GEEKS'
    print (checkEmpty(input, pattern))

true

Complejidad de tiempo: O(n/m) , donde n es la longitud de la string y m es la longitud de la substring
Espacio auxiliar: O(1)