Bold words in string

Array Hash Table String Trie String Matching

52.5% acceptance

Mar 31, 2026

282

124

Given an array of keywords words and a string s, make all appearances of all keywords words[i] in s bold. Any letters between and tags become bold. Return s after adding the bold tags. The returned string should use the least number of tags possible, and the tags should form a valid combination.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

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