L’algoritmo per rendere le parole audaci in HTML

Dato un insieme di parole chiave e una stringa S, rendi tutte le apparenze di tutte le parole chiave in S grassetto. Tutte le lettere tra i tag e diventano in grassetto.

La stringa restituita dovrebbe utilizzare il minor numero possibile di tag e, naturalmente, i tag dovrebbero formare una combinazione valida.

Ad esempio, dato che le parole = ["ab", "bc"] e S = "aabcd", dovremmo restituire "a abc d". Nota che restituire "a a bcd" userebbe più tag, quindi non è corretto.

Nota:

• le parole hanno una lunghezza nell’intervallo [0, 50].
• word[i] ha una lunghezza nell’intervallo [1, 10].
• S ha lunghezza nell’intervallo [0, 500].
• Tutti i caratteri nelle parole[i] e S sono lettere minuscole.

Rendi String Bold usando l’algoritmo Bruteforce

Senza il requisito del più breve, possiamo mettere in grassetto ogni occorrenza delle parole nell’elenco. Poiché ci viene data la stringa HTML originale, possiamo contrassegnare in grassetto ogni carattere che appare nelle parole in grassetto.

Quindi, con O(N) spazio e O(NM) dove N è la dimensione della stringa e M è la lunghezza totale della stringa in grassetto, il seguente algoritmo C++ bruteforce inserirà i meno tag HTML in grassetto che soddisfano il requisito.

Dopo che i caratteri in grassetto sono stati contrassegnati, eseguiamo nuovamente la scansione della stringa e cerchiamo i limiti e inseriamo i tag di conseguenza.