Алгоритм выделения слов жирным шрифтом в 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, которые удовлетворяют требованию.
После того, как жирные символы отмечены, мы повторно сканируем строку и ищем границы, и вставляем теги соответственно.