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.
class Solution {
public:
string boldWords(vector<string>& words, string S) {
int n = S.size();
vector<bool> bold(n, false);
for (const auto &s: words) {
for (int i = 0; i + s.size() - 1 < n; ++ i) {
bool ok = true;
for (int k = 0; k < s.size(); ++ k) {
if (s[k] != S[i + k]) { // bold string s not found in the string
ok = false;
break;
}
}
if (ok) { // it is bold
for (int k = 0; k < s.size(); ++ k) {
bold[i + k] = true; // mark the character bold
}
}
}
}
string ans = "";
for (int i = 0; i < n; ++ i) {
// bold start boundary
if (bold[i] && (i == 0 || !bold[i - 1])) ans += "<b>";
ans += S[i];
// bold end boundary
if (bold[i] && (i == n - 1 || !bold[i + 1])) ans += "</b>";
}
return ans;
}
};Po zaznaczeniu pogrubionych znaków ponownie skanujemy ciąg i szukamy granic, a następnie wstawiamy odpowiednio tagi.