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").