Add bold tag in string

Array Hash Table String Trie String Matching

51.4% acceptance

Mar 31, 2026

1114

203

You are given a string s and an array of strings words. You should add a closed pair of bold tag and to wrap the substrings in s that exist in words. If two such substrings overlap, you should wrap them together with only one pair of closed bold-tag. If two substrings wrapped by bold tags are consecutive, you should combine them. Return s after adding the bold tags.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn add_bold_tag(s: String, words: Vec<String>) -> String {
    let n = s.len();
    let mut bold = vec![false; n];
    for word in &words {
      let wlen = word.len();
      if wlen > n { continue; }
      for i in 0..=n - wlen {
        if &s[i..i + wlen] == word.as_str() {
          for j in i..i + wlen {
            bold[j] = true;
          }
        }
      }
    }
    let mut result = String::new();
    let bytes = s.as_bytes();
    let mut i = 0;
    while i < n {
      if bold[i] {
        result.push_str("<b>");
        while i < n && bold[i] {
          result.push(bytes[i] as char);
          i += 1;
        }
        result.push_str("</b>");
      } else {
        result.push(bytes[i] as char);
        i += 1;
      }
    }
    result
  }
}