Der Algorithmus, um Wörter in HTML fett zu machen

Wenn Sie eine Reihe von Schlüsselwörtern und eine Zeichenfolge S haben, machen Sie alle Vorkommen aller Schlüsselwörter in S fett. Alle Buchstaben zwischen und -Tags werden fett dargestellt.

Die zurückgegebene Zeichenfolge sollte die geringstmögliche Anzahl von Tags verwenden, und natürlich sollten die Tags eine gültige Kombination bilden.

Wenn beispielsweise die Wörter = [„ab“, „bc“] und S = „aabcd“ sind, sollten wir „a abc d“ zurückgeben. Beachten Sie, dass die Rückgabe von „a a bcd“ mehr Tags verwenden würde, also ist es falsch.

Notiz:

• Wörter haben eine Länge im Bereich [0, 50].
• Wörter[i] hat eine Länge im Bereich [1, 10].
• S hat eine Länge im Bereich [0, 500].
• Alle Zeichen in Wörtern [i] und S sind Kleinbuchstaben.

Machen Sie String Bold mit dem Bruteforce-Algorithmus

Ohne die Anforderung des kürzesten können wir jedes Vorkommen der Wörter in der Liste fett darstellen. Da wir den ursprünglichen HTML-String erhalten, können wir jedes Zeichen fett markieren, das in den fett gedruckten Wörtern erscheint.

Mit O(N)-Leerzeichen und O(NM), wobei N die Größe des Strings und M die Gesamtlänge des fettgedruckten Strings ist, fügt der folgende C++- Bruteforce-Algorithmus die wenigsten fettgedruckten HTML-Tags ein, die die Anforderung erfüllen.

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

Nachdem die fettgedruckten Zeichen markiert sind, scannen wir die Zeichenfolge erneut und suchen nach den Grenzen und fügen die Tags entsprechend ein.