## 758. Bold Words in String

Given a set of keywords words and a string S, make all appearances of all keywords in S bold. Any letters between <b> and </b> tags become bold.

The returned string should use the least number of tags possible, and of course the tags should form a valid combination.

For example, given that words = ["ab", "bc"] and S = "aabcd", we should return "a<b>abc</b>d". Note that returning "a<b>a<b>b</b>c</b>d" would use more tags, so it is incorrect.

Constraints:

• words has length in range [0, 50].
• words[i] has length in range [1, 10].
• S has length in range [0, 500].
• All characters in words[i] and S are lowercase letters.

Note: This question is the same as 616: https://leetcode.com/problems/add-bold-tag-in-string/

## Rust Solution

struct Solution;

impl Solution {
fn bold_words(words: Vec<String>, s: String) -> String {
let n = s.len();
let mut bold: Vec<bool> = vec![false; n];
let mut res: String = "".to_string();
for word in words {
let w = word.len();
for i in 0..=(n - w) {
let ss = &s[i..i + w];
if ss == word {
for j in 0..w {
bold[i + j] = true;
}
}
}
}
let s: Vec<char> = s.chars().collect();
for i in 0..n {
if bold[i] && (i == 0 || !bold[i - 1]) {
res += "<b>";
}
res.push(s[i]);
if bold[i] && (i == n - 1 || !bold[i + 1]) {
res += "</b>";
}
}
res
}
}

#[test]
fn test() {
let words: Vec<String> = vec_string!["ab", "bc"];
let s = "aabcd".to_string();
let res = "a<b>abc</b>d".to_string();
assert_eq!(Solution::bold_words(words, s), res);
let words: Vec<String> = vec_string!["e", "cab", "de", "cc", "db"];