Algoritm sõnade paksuks muutmiseks HTML-is

Võttes arvesse märksõnade komplekti sõnad ja stringi S, muutke kõik märksõnad S paksus kirjas. Kõik ja siltide vahel olevad tähed muutuvad paksuks.

Tagastatud string peaks kasutama võimalikult vähe silte ja loomulikult peaksid sildid moodustama kehtiva kombinatsiooni.

Näiteks kui sõnad = ["ab", "bc"] ja S = "aabcd", peaksime tagastama "a abc d". Pange tähele, et "a a bcd" tagastamine kasutaks rohkem silte, nii et see on vale.

Märge:

• sõnade pikkus on vahemikus [0, 50].
• sõnade [i] pikkus on vahemikus [1, 10].
• S pikkus on vahemikus [0, 500].
• Kõik sõnades [i] ja S olevad märgid on väiketähed.

Tehke string paksuks, kasutades Bruteforce’i algoritmi

Ilma lühima nõudeta saame teha paksus kirjas kõik loendis esinevad sõnad. Kuna meile antakse algne HTML-string, saame iga rasvases kirjas esineva märgi puhul märkida paksuks.

Seega, kui O(N) tühik ja O(NM), kus N on stringi suurus ja M on paksus kirjas stringi kogupikkus, lisab järgmine C++ jõhkra jõu algoritm kõige vähem HTML-i paksus kirjas silte, mis vastavad nõudele.

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

Pärast rasvaste märkide märgistamist skannime stringi uuesti ja otsime piirid ning sisestame vastavalt sildid.