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"];
    let s = "cbccceeead".to_string();
    let res = "cb<b>ccceee</b>ad".to_string();
    assert_eq!(Solution::bold_words(words, s), res);
    let words: Vec<String> = vec_string!["ccb", "b", "d", "cba", "dc"];
    let s = "eeaadadadc".to_string();
    let res = "eeaa<b>d</b>a<b>d</b>a<b>dc</b>".to_string();
    assert_eq!(Solution::bold_words(words, s), res);
}

Having problems with this solution? Click here to submit an issue on github.