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.

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;
    }
};

Efter att de fetstilta tecknen är markerade skannar vi strängen igen och letar efter gränserna och infogar taggarna därefter.