El algoritmo para poner palabras en negrita en HTML
Dado un conjunto de palabras clave y una cadena S, haga todas las apariciones de todas las palabras clave en negrita S. Cualquier letra entre las etiquetas y se pone en negrita.
La cadena devuelta debe usar la menor cantidad posible de etiquetas y, por supuesto, las etiquetas deben formar una combinación válida.
Por ejemplo, dado que las palabras = ["ab", "bc"] y S = "aabcd", deberíamos devolver "a abc d". Tenga en cuenta que devolver "a a bcd" usaría más etiquetas, por lo que es incorrecto.
Nota:
- palabras tiene una longitud en el rango [0, 50].
- palabras[i] tiene una longitud en el rango [1, 10].
- S tiene una longitud en el rango [0, 500].
- Todos los caracteres de las palabras [i] y S son letras minúsculas.
Hacer String Bold usando el algoritmo de fuerza bruta
Sin el requisito de la más corta, podemos poner en negrita todas las apariciones de las palabras en la lista. Como se nos da la cadena HTML original, podemos marcar en negrita cada carácter que aparece en las palabras en negrita.
Entonces, con el espacio O(N) y O(NM) donde N es el tamaño de la cadena y M es la longitud total de la cadena en negrita, el siguiente algoritmo de fuerza bruta de C++ insertará la menor cantidad de etiquetas HTML en negrita que satisfagan el requisito.
Después de marcar los caracteres en negrita, volvemos a escanear la cadena y buscamos los límites, e insertamos las etiquetas en consecuencia.