O algoritmo para tornar as palavras em negrito em HTML

Dado um conjunto de palavras-chave e uma string S, faça todas as aparições de todas as palavras-chave em negrito. Quaisquer letras entre e as tags ficam em negrito.

A string retornada deve usar o menor número possível de tags e, claro, as tags devem formar uma combinação válida.

Por exemplo, considerando que palavras = [“ab", “bc”] e S = “aabcd”, devemos retornar “a abc d”. Observe que retornar “a a bcd” usaria mais tags, então está incorreto.

Observação:

• palavras tem comprimento no intervalo [0, 50].
• words[i] tem comprimento no intervalo [1, 10].
• S tem comprimento no intervalo [0, 500].
• Todos os caracteres em words[i] e S são letras minúsculas.

Faça String Bold usando o algoritmo Bruteforce

Sem a exigência do mais curto, podemos colocar negrito em todas as ocorrências das palavras da lista. Como recebemos a string HTML original, podemos marcar em negrito para cada caractere que aparece nas palavras em negrito.

Portanto, com espaço O(N) e O(NM) onde N é o tamanho da string e M é o comprimento total da string em negrito, o algoritmo de força bruta C++ a seguir inserirá as tags HTML em negrito menos que satisfaçam o requisito.

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

Depois que os caracteres em negrito são marcados, redigitalizamos a string e procuramos os limites e inserimos as tags de acordo.