Comparación de Cadenas con Backspaces

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