Algoritmen för att göra ord fet i HTML
Givet en uppsättning nyckelord ord och en sträng S, gör alla uppträdanden av alla nyckelord i fet stil. Alla bokstäver mellan och taggar blir fetstilta.
Den returnerade strängen bör använda minsta möjliga antal taggar, och naturligtvis bör taggarna bilda en giltig kombination.
Till exempel, med tanke på att orden = ["ab", "bc"] och S = "aabcd", bör vi returnera "a abc d". Observera att om du returnerar " a bcd" skulle fler taggar användas, så det är felaktigt.
Notera:
- ord har längd i intervallet [0, 50].
- ord[i] har längd i intervallet [1, 10].
- S har en längd inom området [0, 500].
- Alla tecken i ord[i] och S är små bokstäver.
Gör sträng fet med Bruteforce Algorithm
Utan kravet på det kortaste kan vi göra fetstil på varje förekomst av orden i listan. Eftersom vi får den ursprungliga HTML-strängen kan vi markera fetstil för varje tecken som visas i fetstilta ord.
Så, med O(N)-mellanslag och O(NM) där N är storleken på strängen och M är den totala längden på den fetstilta strängen, kommer följande C++ bruteforce-algoritm att infoga minst HTML-taggar med fet stil som uppfyller kravet.
Efter att de fetstilta tecknen är markerade skannar vi strängen igen och letar efter gränserna och infogar taggarna därefter.