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.
Nachdem die fettgedruckten Zeichen markiert sind, scannen wir die Zeichenfolge erneut und suchen nach den Grenzen und fügen die Tags entsprechend ein.