Add Bold Tag in String

medium string interval

Problem

Given a string s and a list of words, wrap each substring matching any word in …; merge overlapping/contiguous matches.

Inputs='abcxyz123' words=['abc','123']

Output'abcxyz123'

Two non-overlapping matches stay separate.

input

def add_bold(s, words):
    mark = [False] * len(s)
    for w in words:
        i = s.find(w)
        while i != -1:
            for k in range(i, i + len(w)): mark[k] = True
            i = s.find(w, i + 1)
    out, i = [], 0
    while i < len(s):
        if mark[i]:
            j = i
            while j < len(s) and mark[j]: j += 1
            out.append('' + s[i:j] + ''); i = j
        else: out.append(s[i]); i += 1
    return ''.join(out)

function addBold(s, words) {
  const mark = new Array(s.length).fill(false);
  for (const w of words) {
    for (let i = s.indexOf(w); i !== -1; i = s.indexOf(w, i + 1))
      for (let k = i; k < i + w.length; k++) mark[k] = true;
  }
  let out = '', i = 0;
  while (i < s.length) {
    if (mark[i]) {
      let j = i; while (j < s.length && mark[j]) j++;
      out += '' + s.slice(i, j) + ''; i = j;
    } else { out += s[i]; i++; }
  }
  return out;
}

String addBold(String s, String[] words) {
    boolean[] mark = new boolean[s.length()];
    for (String w : words) {
        for (int i = s.indexOf(w); i != -1; i = s.indexOf(w, i + 1))
            for (int k = i; k < i + w.length(); k++) mark[k] = true;
    }
    StringBuilder sb = new StringBuilder();
    int i = 0;
    while (i < s.length()) {
        if (mark[i]) {
            int j = i; while (j < s.length() && mark[j]) j++;
            sb.append("").append(s, i, j).append(""); i = j;
        } else { sb.append(s.charAt(i++)); }
    }
    return sb.toString();
}

string addBold(string s, vector& words) {
    vector mark(s.size(), false);
    for (auto& w : words) {
        size_t i = s.find(w);
        while (i != string::npos) {
            for (size_t k = i; k < i + w.size(); k++) mark[k] = true;
            i = s.find(w, i + 1);
        }
    }
    string out; int i = 0, n = s.size();
    while (i < n) {
        if (mark[i]) {
            int j = i; while (j < n && mark[j]) j++;
            out += "" + s.substr(i, j - i) + ""; i = j;
        } else out += s[i++];
    }
    return out;
}

Explanation

Wrapping matches in  gets tricky when matches overlap or touch. The clean trick is to separate the two concerns: first figure out which indices should be bold, then build the output in one pass.

We make a boolean array mark the same length as s. For every word, we find all of its occurrences and set mark[k] = true for every index k the match covers. Overlapping or adjacent matches just paint over the same array, so they automatically merge into one bold region.

Then we walk s from left to right. When we hit a marked index, we grab the whole contiguous run of marked indices and wrap that slice in .... Unmarked characters are copied as-is.

Example: s = "abcxyz123", words ["abc","123"]. The matches mark indices 0–2 and 6–8. Walking through, the first run becomes abc, then xyz is plain, then 123, giving abcxyz123.

Because merging happens for free in the boolean array, we never have to reason about interval overlaps directly.

Time: O(n · Σ|w|) Space: O(n)