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

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

Повернений рядок має використовувати найменшу можливу кількість тегів, і, звичайно, теги мають утворювати дійсну комбінацію.

Наприклад, враховуючи, що слова = [“ab", “bc”] і S = “aabcd”, ми повинні повернути “a abc d”. Зауважте, що повернення “a a bcd” буде використовувати більше тегів, тому це неправильно.

Примітка:

• слова мають довжину в діапазоні [0, 50].
• words[i] має довжину в діапазоні [1, 10].
• S має довжину в діапазоні [0, 500].
• Усі символи в словах[i] та S є малими літерами.

Зробіть рядок жирним за допомогою алгоритму Bruteforce

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

Отже, з O(N) пробілом і O(NM), де N – розмір рядка, а M – загальна довжина жирного рядка, наступний алгоритм C++ bruteforce вставлятиме найменшу кількість жирних тегів 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;
    }
};

Після виділення жирних символів ми повторно скануємо рядок і шукаємо межі, а також вставляємо теги відповідно.