0

no quiero que me lo hagan solo quiero que me lo explique, lo leo y lo leo pero por más que trato no termino de entender la forma de resolverlo, lo estoy realizando en python.

aqui dejo algo del codigo que estoy realizando

     import re

     def buscar_palabra(palabra, garabatos):  
          for p in palabras:     
              if re.search(p, frase):      

                 print("YES")    

              else:  

                 print("NO") 

       garabatos = '3 hulk mounthulk teddy come coder urredoc'

       palabras = ['hulk', 'coder']  


       buscar_palabra(palabra, garabatos)

introducir la descripción de la imagen aquí

introducir la descripción de la imagen aquí

2
  • 2
    No puedes copiar y pegar el enunciado como texto? Una foto hecha con un móvil a una pantalla es casi ilegible.
    – abulafia
    el 20 ene. 2022 a las 7:50
  • 1
    Además de que deberías traducirlo, pues esto es stack overflow en español
    – abulafia
    el 20 ene. 2022 a las 7:56

2 respuestas 2

0

Problema

Si eliminamos la "literatura" del problema y nos centramos en qué debe hacer el código, se puede resumir en lo siguiente:

  • Dadas dos cadenas en las variables patron y cadena, retornar "YES" si alguna permutación de las letras de patron aparece dentro de cadena, o "NO" en caso contrario.

Por ejempo, si patrón es "foo", y cadena es "enfocado", la respuesta sería "NO", ya que ninguna de las permutaciones de "foo" ("foo", "ofo", "oof") aparece en la cadena "hola". En cambio, si el patrón es "foo" y la cadena es "roof" la respuesta sería "YES" puesto que la permutación "oof" sí que aparece dentro de "roof".

Solución exhaustiva

Del enunciado sale directamente un algoritmo, pero puede llegar a ser extremdamente lento según la longitud de la palabra en patron. El algoritmo sería:

dadas patron y cadena:
  para cada permutacion de letras de patron:
    si la permutacion está en cadena:
       retornar "YES"
  retornar "NO"   # Agotadas todas las opciones

Para enumerar permutaciones se puede usar itertools.permutations() y para ver si una cadena forma parte de otra se puede usar if subcadena in cadena. Es decir, todo esto puede hacerse sin ayuda de expresiones regulares (que de hecho no aportan nada y harían más lenta la comparación).

El problema con esta solución es que el número de permutaciones de N letras es el factorial de N. Esto crece increíblemente deprisa. Si patron tiene 10 letras, N=10, y el número de permutaciones es 3628800. Si podemos probar a una velocidad de 1000 permutaciones por segundo, tardaría 1h en terminar.

Las especificaciones del problema dicen que la longitud de patron es inferior a 1000. Eso es una barbaridad! El factorial de 1000 es un número inimaginable, y se necesitaría más tiempo que la edad del universo para mirarlas todas, aún si pudieramos hacer billones de pruebas por segundo.

Quiero pensar que el dato ese de que la longitud de patron sea inferior a 1000 va encaminado tan sólo a que si haces una implementación en C, el tamaño del array de caracteres para guardar el patrón sea 1000. Es decir, es un dato técnico para que le dés un tamaño a la variable, y no un requisito funcional (que la palabra pueda llegar a tener 1000 caracteres).

¿Algún atajo?

Algunos problemas pueden resolverse sin examinar exhaustivamente todas las combinaciones, si somos capaces a ver algún atajo "ingenioso".

Por desgracia no se me ocurre ninguno para este caso. Algunas ideas más o menos obvias no funcionarán, como la siguiente:

dadas patron y cadena:
  para cada letra de patron:
    si la letra no está en la cadena:
       retornar "NO"
  # Ya hemos mirado y todas las letras están
  retornar "YES"

Este método detecta rápidamente el caso "NO" tan pronto como en el patrón aparezca una letra que no está en la cadena. Por ejemplo si el patron es "HOLA" pero la palabra es "ADIOS", basta con ver que la "H" no está en la palabra para saber que la respuesta será "NO".

En cambio el método falla en el "YES". Por ejemplo si el patrón es "foo" y la cadena es "enfocado" retornaría "YES", porque todas las letras de "foo" aparecen en "enfocado", pero la respuesta debería ser "NO" porque no aparecen en el orden correcto (ni "foo", ni "ofo" ni "oof").

0

he estado viendo el enunciado y el código y según lo que he entendido quieres sacar todas las coincidencias de las palabras hulk y coder de esa cadena (incluyendo 'mounthulk' ya que contiene la palabra 'hulk').

Hacía mucho que veía ni escribía código en python, así que no estoy muy familiarizado ahora mismo pero he intentado resolver el problema.

Lo que he hecho ha sido sacar todas las coincidencias de las dos palabras 'hulk' y 'coder' y ponerlas en una lista parsear todos los elementos de la cadena garabatos en una lista para poder recorrerla e ir comparando cada una de las palabras de garabatos[] con cada una de las coincidencias de la sentencia re.findall. lo siento si no me he explicado con claridad.

Espero que te sirva.

import re

def buscar_palabra(palabras, garabatos):  
    for p in palabras:   
          
        coincidencia = re.findall(p, garabatos)

        if len(coincidencia) != 0: 

            for result in coincidencia:

                for palabra in garabatosParseado:
                    
                    if re.search(palabra, result) != None:

                        print("YES")

                    else:
                        print("NO")        

        else:  

            print("NO HAY VALORES") 

garabatos = "['3', 'hulk', 'mounthulk', 'teddy', 'come', 'coder', 'urredoc']"

garabatosParseado = eval(garabatos)

palabras = ['hulk', 'coder']  


buscar_palabra(palabras, garabatos)
2
  • Dos cosas respecto a tu codigo. Primero re.search(palabra, result) != None se puede cambiar por palabra in result. También eval y exec son peligrosos si procesan cadenas escritas por el usuario, pues podría ejecutarse código malicioso. Te recomiendo cambiar el eval por literal_eval del modulo ast, que solo permite evaluar literales. Por lo demás está perfecto c:
    – Dante S.
    el 20 ene. 2022 a las 13:34
  • Muchas gracias, lo corregiré @DanteS.
    – DQSXE
    el 20 ene. 2022 a las 13:46

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.