Алгоритм выделения слов жирным шрифтом в HTML

Учитывая набор ключевых слов и строку S, выделить все появления всех ключевых слов в S полужирным шрифтом. Любые буквы между тегами и выделяются жирным шрифтом.

Возвращаемая строка должна содержать наименьшее возможное количество тегов, и, конечно же, теги должны образовывать допустимую комбинацию.

Например, учитывая, что слова = ["ab", "bc"] и S = ​​"aabcd", мы должны вернуть "a abc d". Обратите внимание, что при возврате " a b cd" потребуется больше тегов, так что это неправильно.

Примечание:

• слова имеют длину в диапазоне [0, 50].
• words[i] имеет длину в диапазоне [1, 10].
• S имеет длину в диапазоне [0, 500].
• Все символы в словах[i] и S являются строчными буквами.

Сделать строку полужирной, используя алгоритм грубой силы

Без требования кратчайшего пути мы можем выделить жирным шрифтом все вхождения слов в списке. Поскольку нам дана исходная строка HTML, мы можем выделить жирным шрифтом каждый символ, который появляется в выделенных жирным шрифтом словах.

Таким образом, при O(N) пробеле и O(NM), где N — размер строки, а M — общая длина строки, выделенной жирным шрифтом, следующий алгоритм перебора C++ будет вставлять наименьшее количество тегов полужирного HTML, которые удовлетворяют требованию.

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

После того, как жирные символы отмечены, мы повторно сканируем строку и ищем границы, и вставляем теги соответственно.