Kun on annettu joukko avainsanoja sanoja ja merkkijono S, tee kaikki avainsanat S lihavoidulla. Kaikki ja -tunnisteiden väliset kirjaimet lihavoittuvat.
Palautettavan merkkijonon tulee käyttää mahdollisimman vähän tageja, ja tietysti tagien tulee muodostaa kelvollinen yhdistelmä.
Koska esimerkiksi sanat = ["ab", "bc"] ja S = "aabcd", meidän pitäisi palauttaa "a abc d". Huomaa, että "a a bcd":n palauttaminen käyttäisi enemmän tageja, joten se on väärin.
merkintä:
- sanojen pituus on alueella [0, 50].
- sanojen [i] pituus on alueella [1, 10].
- S:n pituus on alueella [0, 500].
- Kaikki merkit sanoissa[i] ja S ovat pieniä kirjaimia.
Lihavoita merkkijonoa käyttämällä Bruteforce-algoritmia
Ilman lyhimmän vaatimusta voimme lihavoida kaikki luettelon sanat. Koska saamme alkuperäisen HTML-merkkijonon, voimme merkitä lihavoinnin jokaiselle lihavoidussa sanassa näkyvälle merkille.
Joten O(N) välilyönnillä ja O(NM):llä, jossa N on merkkijonon koko ja M on lihavoitun merkkijonon kokonaispituus, seuraava C++ bruteforce -algoritmi lisää vähiten vaatimuksen täyttäviä HTML-lihavoituja tageja.
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;
}
};Kun lihavoidut merkit on merkitty, skannaamme merkkijonon uudelleen ja etsimme rajat ja lisäämme tunnisteet vastaavasti.