Mając zestaw słów kluczowych, słowa i ciąg S, pogrub wszystkie wystąpienia wszystkich słów kluczowych. Wszelkie litery pomiędzy i tagami stają się pogrubione.
Zwracany ciąg powinien używać jak najmniejszej możliwej liczby tagów i oczywiście tagi powinny tworzyć prawidłową kombinację.
Na przykład, biorąc pod uwagę, że słowa = [„ab", „bc”] i S = „aabcd”, powinniśmy zwrócić „a abc d”. Zwróć uwagę, że zwrócenie „a a bcd” spowoduje użycie większej liczby tagów, więc to jest niepoprawne.
Notatka:
- słowa mają długość w zakresie [0, 50].
- słowa[i] mają długość w przedziale [1, 10].
- S ma długość w przedziale [0,500].
- Wszystkie znaki w słowach[i] i S są małymi literami.
Pogrubienie ciągu za pomocą algorytmu Bruteforce
Bez wymogu najkrótszego, możemy pogrubić każde wystąpienie słów na liście. Ponieważ otrzymaliśmy oryginalny ciąg HTML, możemy zaznaczyć pogrubienie dla każdego znaku występującego w pogrubionych słowach.
Tak więc, z przestrzenią O(N) i O(NM), gdzie N jest rozmiarem ciągu, a M jest całkowitą długością pogrubionego ciągu, następujący algorytm bruteforce C++ wstawi najmniej pogrubionych tagów HTML, które spełniają wymagania.
Po zaznaczeniu pogrubionych znaków ponownie skanujemy ciąg i szukamy granic, a następnie wstawiamy odpowiednio tagi.