Алгоритм виділення слів жирним шрифтом у 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, які задовольняють вимозі.
Після виділення жирних символів ми повторно скануємо рядок і шукаємо межі, а також вставляємо теги відповідно.