Comparación de Cadenas con Backspaces

Clase 29 de 41 • Curso de Algoritmos Avanzados: Estructuras de Datos Lineales

Contenido del curso

Introducción

1
¿Ya tomaste el Curso Avanzado de Algoritmos: Patrones de Arrays y Strings?
00:52 min

Lista Enlazada

Pilas y colas

Colas de prioridad

Próximos pasos

41
Toma el Curso Avanzado de Algoritmos: Grafos y Árboles
00:33 min

Tomar examen

Ejercicios resueltos de Pilas

Comparación de Cadenas con Backspaces

Dadas dos cadenas s y t, devuelve true si son iguales cuando ambas se escriben en editores de texto vacíos. '#' significa un carácter de backspace (tecla de restroceso). En el caso de retroceder en una cadena vacía, esta continuará vacía.

Ejemplo 1:
    Entrada: s = "ab#c", t = "ad#c"
    Salida: true
Explicación: Tanto s como t se convierten en "ac".

Ejemplo 2:
    Entrada: s = "ab##", t = "c#d#"
    Salida: verdadero
Explicación: Tanto s como t se convierten en "".

def comparacion_backspace(self, string: str, T: str) -> bool:
   if not string or not T:
       return False
   pilaS = []
   pilaT = []
   for caracter in string:
       if caracter == "#":
           if pilaS:
               pilaS.pop()
       else:
           pilaS.append(caracter)
   for caracter in T:
       if caracter == "#":
           if pilaT:
               pilaT.pop()
       else:
           pilaT.append(caracter) 
   return pilaT == pilaS

Eliminar Subcarpetas del Sistema de Archivos

Dada una lista de carpetas, devuelva las carpetas después de eliminar todas las subcarpetas de esas carpetas. Puede devolver la respuesta en cualquier orden.

Si una carpeta[i] se encuentra dentro de otra carpeta[j], se denomina subcarpeta de ésta.

El formato de una ruta es una o varias cadenas concatenadas de la forma '/' seguida de una o varias letras inglesas minúsculas.

Por ejemplo, "/carpeta1" y "/carpeta1/problemas" son rutas válidas, mientras que una cadena vacía y "/" no lo son.

Ejemplo 1:
    Entrada: carpeta = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
    Salida: ["/a","/c/d","/c/f"]
Explicación: Las carpetas "/a/b" es una subcarpeta de "/a" y "/c/d/e" está dentro de la carpeta "/c/d" en nuestro sistema de archivos.


Ejemplo 2:
    Entrada: carpeta = ["/a","/a/b/c","/a/b/d"]
    Salida: ["/a"]
Explicación: Las carpetas "/a/b/c" y "/a/b/d" serán eliminadas porque son subcarpetas de "/a".

def removeSubfolders(self, carpeta: List[str]) -> List[str]:
   carpeta.sort()
   respuesta = [carpeta[0]]
   for i in range(1, len(carpeta)):
       if not carpeta[i].startswith(respuesta[-1]+'/'):
           respuesta.append(carpeta[i])
   return respuesta

Simplificar Rutas

Dada una cadena que representa una ruta absoluta, es decir que representa la ruta de archivo o directorio en un sistema de archivos estilo Unix (comienza con un slash '/'), conviértala en la ruta canónica simplificada.

En un sistema de archivos de estilo Unix, un punto '.' se refiere al directorio actual, un doble punto '..' se refiere al directorio de un nivel superior, y cualquier barra múltiple consecutiva (es decir, '//') se trata como una sola barra '/'. Para este problema, cualquier otro formato de puntos como '...' se tratan como nombres de archivo/directorio.

La ruta canónica debe tener el siguiente formato: La ruta comienza con una sola barra '/'. Dos directorios cualesquiera se separan con una sola barra '/'. La ruta no termina con un "/" al final. La ruta sólo contiene los directorios de la ruta desde el directorio raíz hasta el archivo o directorio de destino (es decir, sin punto '.' o doble punto '..') Devuelve la ruta canónica simplificada.

Ejemplo 1:
    Entrada: ruta = "/home/"
    Salida: "/home"
Explicación: Observe que no hay una barra al final del nombre del último directorio.


Ejemplo 2:
    Entrada: ruta = "/../"
    Salida: "/"
Explicación: Subir un nivel desde el directorio raíz es un no-op, ya que el nivel raíz es el nivel más alto al que se puede ir.


Ejemplo 3:
    Entrada: path = "/home//foo/"
    Salida: "/home/foo"
Explicación: En la ruta canónica, varias barras inclinadas consecutivas se sustituyen por una sola.

def simplificar(self, ruta: str) -> str:
   pila = []
   lista_rutas = ruta.split('/')
   for fragmento in lista_rutas:
       if fragmento == '..':
           if pila:
               pila.pop()
       elif fragmento == '.' or fragmento == '':
           continue
       else:
           pila.append(fragmento)

   nueva_ruta = '/'
   for i in range(len(pila)):
       nueva_ruta += pila[i]
       if i < len(pila) - 1:
           nueva_ruta += '/'
   return nueva_ruta

Calculadora Dada una cadena s que representa una expresión, evaluar esta expresión y devolver su valor. La división de enteros debe truncar hacia cero. Puede asumir que la expresión dada es siempre válida. Todos los resultados intermedios estarán en el rango de [-231, 231 - 1].

Nota: No está permitido utilizar ninguna función incorporada que evalúe cadenas como expresiones matemáticas, como eval().

Ejemplo 1:
Entrada: s = "3+2*2"
Salida: 7

Ejemplo 2:
Entrada: s = " 3/2 "
Salida: 1

Ejemplo 3:
Entrada: s = " 3+5 / 2 "
Salida: 5

def calculadora(self, string: str) -> int:
   string = string.replace(' ', '')
   pila = []
   numeroActual = 0
   operador = '+'
   string = string + '+'
   for caracter in string:
       if caracter.isdigit():
           numeroActual=numeroActual * 10 + int(caracter)
       else:
           if operador is '+':
               pila.append(numeroActual)
           elif operador is '-':
               pila.append(-numeroActual)
           elif operador is '*':
               pila[-1] *= numeroActual
           elif operador is '/':
               pila[-1] = int(float(pila[-1])/numeroActual) 
           numeroActual = 0
           operador = caracter
   return sum(pila)

Dividir Palabras

Dada una cadena s y un diccionario de cadenas wordDict, devuelve true si s puede segmentarse en una secuencia separada por espacios de una o más palabras del diccionario. Tenga en cuenta que la misma palabra del diccionario puede reutilizarse varias veces en la segmentación.

 Ejemplo 1:
    Entrada: s = "leetcode", wordDict = ["leet", "code"]
    Salida: true
Explicación: Devuelve true porque "leetcode" puede ser segmentado como "leet code".

Ejemplo 2:
    Entrada: s = "manzana-manzana", wordDict = ["manzana", "pluma"]
    Salida: true
Explicación: Devuelve true porque "manzana-manzana" se puede segmentar como "manzana-bolígrafo-manzana". (Tenga en cuenta que se permite reutilizar una palabra del diccionario).

def dividirPalabras(self, s: str, wordDict: List[str]) -> bool:
   inicio = 0
   pila = [inicio]
   visitado = set()
   while pila:
       inicio = pila.pop()
       if inicio in visitado:
           continue
       visitado.add(inicio)
       for word in wordDict:

           if s[inicio:].startswith(word):
               x = len(word)
               if x == len(s[inicio:]):
                   return True
               pila.append(inicio + x)
   return False

Comentarios

Yojan Antonio Pardo Zabala

student•

comparto mis soluciones en java utilizando la clase Stack.

public class CompararCadenasConBackspaces {

    public static void main(String[] args) {
        
        final String text1 = "ab#c";
        final String text2 = "abc";

        System.out.printf("Strings %s and %s are equals: %b\n", text1, text2, compareStrings(text1, text2));
    }

    private static boolean compareStrings(final String text1, final String text2) {
        final Stack<Character> stack1, stack2;

        stack1 = stringToCharStackWithBackSpaces(text1);

        stack2 = stringToCharStackWithBackSpaces(text2);

        return stack1.equals(stack2);
    }

    private static Stack<Character> stringToCharStackWithBackSpaces(final String text1) {
        final Stack<Character> stack = new Stack<>();

        for(char c : text1.toCharArray()){
            if(c == '#'){
                stack.pop();
            } else {
                stack.push(c);
            }
        }

        return stack;
    }
}

public class RemoverSubCarpetas {

    final static String[] carpetas = {"/a", "/a/b", "/a/b/c", "/e", "/e/d"};

    public static void main(String[] args) {
        
        final List<String> carpetasRaiz = encontrarCarpetasRaiz(carpetas);

        carpetasRaiz.forEach(System.out::println);
    }

    private static List<String> encontrarCarpetasRaiz(String[] carpetas) {
        final Stack<String> carpetasRaiz = new Stack<>();
        
        Arrays.sort(carpetas);

        for(String carpeta : carpetas){
            if (carpetasRaiz.isEmpty() || !carpeta.startsWith(carpetasRaiz.peek() + '/')){
                carpetasRaiz.push(carpeta);
            }
        }

        return new ArrayList<>(carpetasRaiz);
    }
}
```&#x20;

public class SimplificarRutas {

    public static void main(String[] args) {
        final String ruta = "/../Users/yojan/../documents";
        System.out.printf("Optimized path for [%s] is: [%s]", ruta, optimizePath(ruta));
    }

    private static String optimizePath(String ruta) {
        final Stack<String> optimizedRoute = new Stack<>();
        final String[] chunks = ruta.split("/");

        optimizedRoute.push("");

        for(String chunk : chunks){
            if(chunk.equals("..") && !optimizedRoute.peek().isEmpty()){
                optimizedRoute.pop();
                continue;
            }
            if(!chunk.equals("..") && !chunk.equals(".") && !chunk.equals("")){
                optimizedRoute.push(chunk);
            }
        }

        return optimizedRoute.stream()
                .reduce((acc, e) -> acc + "/" + e)
                .orElse("");
    }
}

public class Calculadora {

    public static void main(String[] args) {
        final Scanner scanner = new Scanner(System.in);
        System.out.println("Insert the operation");
        final String operation = scanner.nextLine();

        System.out.printf("The result for operation [%s] is: %d", operation, resolve(operation));
    }

    private static int resolve(String operation) {
        if(Objects.isNull(operation) || operation.isBlank()){
            System.out.println("this operation is null or blank");
            return 0;
        }

        Stack<Integer> stack = new Stack<>();
        int currentNumber = 0;
        char operationSymbol = '+';

        for(int i = 0; i < operation.length(); i++){
            char c = operation.charAt(i);

            if(Character.isDigit(c)){
                currentNumber = (currentNumber * 10) + (c - '0');
            }

            if(!Character.isDigit(c) && !Character.isWhitespace(c) || i == operation.length() -1){
                switch (operationSymbol) {
                    case '-' -> stack.push(-currentNumber);
                    case '+' -> stack.push(currentNumber);
                    case '*' -> stack.push(stack.pop() * currentNumber);
                    case '/' -> stack.push(stack.pop() / currentNumber);
                }

                operationSymbol = c;
                currentNumber = 0;
            }
        }

        int result = 0;

        while(!stack.isEmpty()) {
            result += stack.pop();
        }

        return result;
    }
}
```&#x20;

Ejemplo 1:
    Entrada: s = "ab#c", t = "ad#c"
    Salida: true
Explicación: Tanto s como t se convierten en "ac".

Ejemplo 2:
    Entrada: s = "ab##", t = "c#d#"
    Salida: verdadero
Explicación: Tanto s como t se convierten en "".

def comparacion_backspace(self, string: str, T: str) -> bool:
   if not string or not T:
       return False
   pilaS = []
   pilaT = []
   for caracter in string:
       if caracter == "#":
           if pilaS:
               pilaS.pop()
       else:
           pilaS.append(caracter)
   for caracter in T:
       if caracter == "#":
           if pilaT:
               pilaT.pop()
       else:
           pilaT.append(caracter) 
   return pilaT == pilaS

Ejemplo 1:
    Entrada: carpeta = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
    Salida: ["/a","/c/d","/c/f"]
Explicación: Las carpetas "/a/b" es una subcarpeta de "/a" y "/c/d/e" está dentro de la carpeta "/c/d" en nuestro sistema de archivos.


Ejemplo 2:
    Entrada: carpeta = ["/a","/a/b/c","/a/b/d"]
    Salida: ["/a"]
Explicación: Las carpetas "/a/b/c" y "/a/b/d" serán eliminadas porque son subcarpetas de "/a".

def removeSubfolders(self, carpeta: List[str]) -> List[str]:
   carpeta.sort()
   respuesta = [carpeta[0]]
   for i in range(1, len(carpeta)):
       if not carpeta[i].startswith(respuesta[-1]+'/'):
           respuesta.append(carpeta[i])
   return respuesta

Ejemplo 1:
    Entrada: ruta = "/home/"
    Salida: "/home"
Explicación: Observe que no hay una barra al final del nombre del último directorio.


Ejemplo 2:
    Entrada: ruta = "/../"
    Salida: "/"
Explicación: Subir un nivel desde el directorio raíz es un no-op, ya que el nivel raíz es el nivel más alto al que se puede ir.


Ejemplo 3:
    Entrada: path = "/home//foo/"
    Salida: "/home/foo"
Explicación: En la ruta canónica, varias barras inclinadas consecutivas se sustituyen por una sola.

def simplificar(self, ruta: str) -> str:
   pila = []
   lista_rutas = ruta.split('/')
   for fragmento in lista_rutas:
       if fragmento == '..':
           if pila:
               pila.pop()
       elif fragmento == '.' or fragmento == '':
           continue
       else:
           pila.append(fragmento)

   nueva_ruta = '/'
   for i in range(len(pila)):
       nueva_ruta += pila[i]
       if i < len(pila) - 1:
           nueva_ruta += '/'
   return nueva_ruta

def calculadora(self, string: str) -> int:
   string = string.replace(' ', '')
   pila = []
   numeroActual = 0
   operador = '+'
   string = string + '+'
   for caracter in string:
       if caracter.isdigit():
           numeroActual=numeroActual * 10 + int(caracter)
       else:
           if operador is '+':
               pila.append(numeroActual)
           elif operador is '-':
               pila.append(-numeroActual)
           elif operador is '*':
               pila[-1] *= numeroActual
           elif operador is '/':
               pila[-1] = int(float(pila[-1])/numeroActual) 
           numeroActual = 0
           operador = caracter
   return sum(pila)

 Ejemplo 1:
    Entrada: s = "leetcode", wordDict = ["leet", "code"]
    Salida: true
Explicación: Devuelve true porque "leetcode" puede ser segmentado como "leet code".

Ejemplo 2:
    Entrada: s = "manzana-manzana", wordDict = ["manzana", "pluma"]
    Salida: true
Explicación: Devuelve true porque "manzana-manzana" se puede segmentar como "manzana-bolígrafo-manzana". (Tenga en cuenta que se permite reutilizar una palabra del diccionario).

def dividirPalabras(self, s: str, wordDict: List[str]) -> bool:
   inicio = 0
   pila = [inicio]
   visitado = set()
   while pila:
       inicio = pila.pop()
       if inicio in visitado:
           continue
       visitado.add(inicio)
       for word in wordDict:

           if s[inicio:].startswith(word):
               x = len(word)
               if x == len(s[inicio:]):
                   return True
               pila.append(inicio + x)
   return False

public class CompararCadenasConBackspaces {

    public static void main(String[] args) {
        
        final String text1 = "ab#c";
        final String text2 = "abc";

        System.out.printf("Strings %s and %s are equals: %b\n", text1, text2, compareStrings(text1, text2));
    }

    private static boolean compareStrings(final String text1, final String text2) {
        final Stack<Character> stack1, stack2;

        stack1 = stringToCharStackWithBackSpaces(text1);

        stack2 = stringToCharStackWithBackSpaces(text2);

        return stack1.equals(stack2);
    }

    private static Stack<Character> stringToCharStackWithBackSpaces(final String text1) {
        final Stack<Character> stack = new Stack<>();

        for(char c : text1.toCharArray()){
            if(c == '#'){
                stack.pop();
            } else {
                stack.push(c);
            }
        }

        return stack;
    }
}

public class RemoverSubCarpetas {

    final static String[] carpetas = {"/a", "/a/b", "/a/b/c", "/e", "/e/d"};

    public static void main(String[] args) {
        
        final List<String> carpetasRaiz = encontrarCarpetasRaiz(carpetas);

        carpetasRaiz.forEach(System.out::println);
    }

    private static List<String> encontrarCarpetasRaiz(String[] carpetas) {
        final Stack<String> carpetasRaiz = new Stack<>();
        
        Arrays.sort(carpetas);

        for(String carpeta : carpetas){
            if (carpetasRaiz.isEmpty() || !carpeta.startsWith(carpetasRaiz.peek() + '/')){
                carpetasRaiz.push(carpeta);
            }
        }

        return new ArrayList<>(carpetasRaiz);
    }
}
```&#x20;

public class SimplificarRutas {

    public static void main(String[] args) {
        final String ruta = "/../Users/yojan/../documents";
        System.out.printf("Optimized path for [%s] is: [%s]", ruta, optimizePath(ruta));
    }

    private static String optimizePath(String ruta) {
        final Stack<String> optimizedRoute = new Stack<>();
        final String[] chunks = ruta.split("/");

        optimizedRoute.push("");

        for(String chunk : chunks){
            if(chunk.equals("..") && !optimizedRoute.peek().isEmpty()){
                optimizedRoute.pop();
                continue;
            }
            if(!chunk.equals("..") && !chunk.equals(".") && !chunk.equals("")){
                optimizedRoute.push(chunk);
            }
        }

        return optimizedRoute.stream()
                .reduce((acc, e) -> acc + "/" + e)
                .orElse("");
    }
}

public class Calculadora {

    public static void main(String[] args) {
        final Scanner scanner = new Scanner(System.in);
        System.out.println("Insert the operation");
        final String operation = scanner.nextLine();

        System.out.printf("The result for operation [%s] is: %d", operation, resolve(operation));
    }

    private static int resolve(String operation) {
        if(Objects.isNull(operation) || operation.isBlank()){
            System.out.println("this operation is null or blank");
            return 0;
        }

        Stack<Integer> stack = new Stack<>();
        int currentNumber = 0;
        char operationSymbol = '+';

        for(int i = 0; i < operation.length(); i++){
            char c = operation.charAt(i);

            if(Character.isDigit(c)){
                currentNumber = (currentNumber * 10) + (c - '0');
            }

            if(!Character.isDigit(c) && !Character.isWhitespace(c) || i == operation.length() -1){
                switch (operationSymbol) {
                    case '-' -> stack.push(-currentNumber);
                    case '+' -> stack.push(currentNumber);
                    case '*' -> stack.push(stack.pop() * currentNumber);
                    case '/' -> stack.push(stack.pop() / currentNumber);
                }

                operationSymbol = c;
                currentNumber = 0;
            }
        }

        int result = 0;

        while(!stack.isEmpty()) {
            result += stack.pop();
        }

        return result;
    }
}
```&#x20;

Comparación de Cadenas con Backspaces

Introducción

¿Ya tomaste el Curso Avanzado de Algoritmos: Patrones de Arrays y Strings?

Lista Enlazada

Estructura de datos: Lista Enlazada

Programando listas enlazadas con Java

Cómo Invertir una Lista Enlazada

Odd Even Linked List: análisis del problema

Solución de Odd Even Linked List

Playground: Odd Even Liked List

Programando Odd Even Linked List con C++

Linked List Cycle: análisis del problema

Solución de Linked List Cycle

Playground: Linked List Cycle

Programando Linked List Cycle con Python

Palindrome Linked List: análisis del problema

Solución de Palindrome Linked List

Playground: Palindrome Linked List

Programando Palindrome Linked List con Java

Reorder List: análisis del problema

Solución de Reorder List

Programando Reorder List con JavaScript

Playground: Reorder List Without Repeated Values

Reto: LRU Caché

Ejercicios Prácticos con Listas Enlazadas y Historial de Navegador

Operaciones con Listas Enlazadas: Suma, Intercambio y Navegador

Pilas y colas

Estructura de datos: Pilas y Colas

Paréntesis Válido: análisis del problema

Solución de Paréntesis Válido

Playground: Paréntesis Válido

Programando Paréntesis Válido con C++