Compruebe si dos strings después de procesar el carácter de retroceso son iguales o no

Dadas dos strings s1 y s2 , supongamos que al escribir las strings se encontraron algunos espacios de retroceso que están representados por # . La tarea es determinar si las strings resultantes después de procesar el carácter de retroceso serían iguales o no.

Ejemplos:  

Entrada: s1= geee#e#ks, s2 = gee##eeks 
Salida: Verdadero 
Explicación: Ambas strings después de procesar el carácter de retroceso se convierten en “geeeeks”. Por lo tanto, cierto.

Entrada: s1 = equ#ual, s2 = ee#quaal#
Salida:  Falso
Explicación: La string 1 después de procesar el carácter de retroceso se convierte en «igual» mientras que la string 2 es «eequaal». Por lo tanto, falso.

Enfoque:
Para resolver el problema mencionado anteriormente, debemos observar que si el primer carácter es ‘#’ , es decir, ciertamente no hay ningún carácter escrito inicialmente y, por lo tanto, no realizamos ninguna operación. Cuando encontramos cualquier carácter que no sea ‘#’ , agregamos el carácter justo después del índice actual. Cuando encontramos un ‘#’ , movemos un índice hacia atrás, así que en lugar de eliminar el carácter, simplemente lo ignoramos. Luego, finalmente compare las dos strings comparando cada carácter de principio a fin.

A continuación se muestra la implementación del enfoque anterior: 

/* C++ implementation to Check if
two strings after processing
backspace character are equal or not*/
 
#include <bits/stdc++.h>
using namespace std;
 
// function to compare the two strings
string removeBackspaces(string& s)
{
    int n = s.size();
 
    // To point at position after considering the
    // backspaces
    int idx = 0;
 
    for (int i = 0; i < n; i++) {
        if (s[i] != '#') {
            s[idx] = s[i];
            idx++;
        }
        else if (s[i] == '#' && idx >= 0) {
            idx--;
        }
 
        // This idx can never point at negative index
        // position
        if (idx < 0)
            idx = 0;
    }
 
    return s.substr(0, idx);
}
 
// Driver code
int main()
{
    // initialise two strings
    string s = "equ#ual";
    string t = "gee##eeks";
 
    if (removeBackspaces(s) == removeBackspaces(t))
        cout << "True";
    else
        cout << "False";
 
    return 0;
}

# Python implementation to Check if two strings after processing backspace character are equal or not
 
# function to compare the two strings
def removeBackspace(s) -> str:
    n = len(s)
    # To point at position after considering the backspaces
    idx = 0
    for i in range(0, n):
        if(s[i] != '#'):
            s = s[:idx] + s[i] + s[idx+1:]
            idx += 1
        elif(s[i] == '#' and idx >= 0):
            idx -= 1
        # This idx can never point at negative index position
        if(idx < 0):
            idx = 0
    ans = ""
    for i in range(0, idx):
        ans += s[i]
    return ans
 
 
# Driver code
s = "equ#ual"
t = "gee##eeks"
if(removeBackspace(s) == removeBackspace(t)):
      print("TRUE")
else:
    print("FALSE")

True

Complejidad temporal: O(N) 
Espacio auxiliar: O(1)
 

Otro enfoque: (usando la pila)
La idea es usar una pila que almacene la última aparición de un carácter que no sea «#» (es decir, Retroceso) e iterar sobre cada string dada y si encontramos algún carácter que no sea ‘#’ luego seguimos almacenándolo en la pila; de lo contrario, eliminamos el último carácter que se almacena en la pila. Realice el proceso Similar para ambas strings dadas y verifique si ambas strings son iguales, luego imprima «Sí» , de lo contrario , «No» .

La siguiente es la implementación del enfoque anterior:

# Python implementation to Check if
# two strings after processing
# backspace character are equal or not
 
# function to compare the two strings
def compare(s, t):
    # function to remove backspaces and return refined string
    def remove_backspace(string):
        a = []
        for i in string:
            if i != "#":
                a.append(i)
            else:
                if len(a):
                    a.pop()
        return "".join(a)
 
    s, t = remove_backspace(s), remove_backspace(t) #remove backspaces from the strings
 
    return s == t #return True if they are euwal
 
# Driver code
 
 
# initialise two strings
s = "geee#e#ks"
t = "gee##eeks"
 
if (compare(s, t)):
    print("True")
else:
    print("False")
 
 
# This code is Contributed by Vivek Maddeshiya

True

Complejidad de tiempo: O(n), donde n es la longitud de la string dada
Espacio auxiliar: O(n)