Skip to content

616. Add Bold Tag in String 👍

Approach 1: Bold boolean array

  • Time: $O(|\texttt{s}|^2 \cdot \Sigma |\texttt{words[i]}|)$
  • Space: $O(|\texttt{s}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
 public:
  string addBoldTag(string s, vector<string>& words) {
    const int n = s.length();
    string ans;
    // bold[i] := true if s[i] should be bolded
    vector<bool> bold(n);

    int boldEnd = -1;  // s[i:boldEnd] should be bolded
    for (int i = 0; i < n; ++i) {
      for (const string& word : words)
        if (s.substr(i).find(word) == 0)  // StartsWith
          boldEnd = max(boldEnd, i + static_cast<int>(word.length()));
      bold[i] = boldEnd > i;
    }

    // Construct the string with the bold tags.
    int i = 0;
    while (i < n)
      if (bold[i]) {
        int j = i;
        while (j < n && bold[j])
          ++j;
        // `s[i..j)` should be bolded.
        ans += "<b>" + s.substr(i, j - i) + "</b>";
        i = j;
      } else {
        ans += s[i++];
      }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
  public String addBoldTag(String s, String[] words) {
    final int n = s.length();
    StringBuilder sb = new StringBuilder();
    // bold[i] := true if s[i] should be bolded
    boolean[] bold = new boolean[n];

    int boldEnd = -1; // s[i:boldEnd] should be bolded
    for (int i = 0; i < n; ++i) {
      for (final String word : words)
        if (s.substring(i).startsWith(word))
          boldEnd = Math.max(boldEnd, i + word.length());
      bold[i] = boldEnd > i;
    }

    // Construct the string with the bold tags.
    int i = 0;
    while (i < n)
      if (bold[i]) {
        int j = i;
        while (j < n && bold[j])
          ++j;
        // s[i..j) should be bolded
        sb.append("<b>").append(s.substring(i, j)).append("</b>");
        i = j;
      } else {
        sb.append(s.charAt(i++));
      }

    return sb.toString();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
  def addBoldTag(self, s: str, words: List[str]) -> str:
    n = len(s)
    ans = []
    # bold[i] := True if s[i] should be bolded
    bold = [0] * n

    boldEnd = -1  # s[i:boldEnd] should be bolded
    for i in range(n):
      for word in words:
        if s[i:].startswith(word):
          boldEnd = max(boldEnd, i + len(word))
      bold[i] = boldEnd > i

    # Construct the with bold tags
    i = 0
    while i < n:
      if bold[i]:
        j = i
        while j < n and bold[j]:
          j += 1
        # `s[i..j)` should be bolded.
        ans.append('<b>' + s[i:j] + '</b>')
        i = j
      else:
        ans.append(s[i])
        i += 1

    return ''.join(ans)

Approach 2: Trie

  • Time: $O(|\texttt{s}|^2 + \Sigma |\texttt{words[i]}|)$
  • Space: $O(|\texttt{s}| + |\texttt{words}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
struct TrieNode {
  vector<shared_ptr<TrieNode>> children;
  bool isWord = false;
  TrieNode() : children(128) {}
};

class Solution {
 public:
  string addBoldTag(string s, vector<string>& words) {
    const int n = s.length();
    string ans;
    // bold[i] := true if s[i] should be bolded
    vector<bool> bold(n);

    for (const string& word : words)
      insert(word);

    int boldEnd = -1;  // `s[i..boldEnd]` should be bolded.
    for (int i = 0; i < n; ++i) {
      boldEnd = max(boldEnd, find(s, i));
      bold[i] = boldEnd >= i;
    }

    // Construct the string with the bold tags.
    int i = 0;
    while (i < n)
      if (bold[i]) {
        int j = i;
        while (j < n && bold[j])
          ++j;
        // `s[i..j)` should be bolded.
        ans += "<b>" + s.substr(i, j - i) + "</b>";
        i = j;
      } else {
        ans += s[i++];
      }

    return ans;
  }

 private:
  shared_ptr<TrieNode> root = make_shared<TrieNode>();

  void insert(const string& word) {
    shared_ptr<TrieNode> node = root;
    for (const char c : word) {
      if (node->children[c] == nullptr)
        node->children[c] = make_shared<TrieNode>();
      node = node->children[c];
    }
    node->isWord = true;
  }

  int find(const string& s, int i) {
    shared_ptr<TrieNode> node = root;
    int ans = -1;
    for (int j = i; j < s.length(); ++j) {
      if (node->children[s[j]] == nullptr)
        return ans;
      node = node->children[s[j]];
      if (node->isWord)
        ans = j;
    }
    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class TrieNode {
  public TrieNode[] children = new TrieNode[128];
  public boolean isWord = false;
}

class Solution {
  public String addBoldTag(String s, String[] words) {
    final int n = s.length();
    StringBuilder sb = new StringBuilder();
    // bold[i] := true if s[i] should be bolded
    boolean[] bold = new boolean[n];

    for (final String word : words)
      insert(word);

    int boldEnd = -1; // `s[i..boldEnd]` should be bolded.
    for (int i = 0; i < n; ++i) {
      boldEnd = Math.max(boldEnd, find(s, i));
      bold[i] = boldEnd >= i;
    }

    // Construct the string with the bold tags.
    int i = 0;
    while (i < n)
      if (bold[i]) {
        int j = i;
        while (j < n && bold[j])
          ++j;
        // s[i..j) should be bolded
        sb.append("<b>").append(s.substring(i, j)).append("</b>");
        i = j;
      } else {
        sb.append(s.charAt(i++));
      }

    return sb.toString();
  }

  private TrieNode root = new TrieNode();

  private void insert(final String word) {
    TrieNode node = root;
    for (final char c : word.toCharArray()) {
      if (node.children[c] == null)
        node.children[c] = new TrieNode();
      node = node.children[c];
    }
    node.isWord = true;
  }

  private int find(final String s, int i) {
    TrieNode node = root;
    int ans = -1;
    for (int j = i; j < s.length(); ++j) {
      if (node.children[s.charAt(j)] == null)
        return ans;
      node = node.children[s.charAt(j)];
      if (node.isWord)
        ans = j;
    }
    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class TrieNode:
  def __init__(self):
    self.children: Dict[str, TrieNode] = {}
    self.isWord = False


class Solution:
  def addBoldTag(self, s: str, words: List[str]) -> str:
    n = len(s)
    ans = []
    # bold[i] := True if s[i] should be bolded
    bold = [0] * n
    root = TrieNode()

    def insert(word: str) -> None:
      node = root
      for c in word:
        node = node.children.setdefault(c, TrieNode())
      node.isWord = True

    def find(s: str, i: int) -> int:
      node = root
      ans = -1
      for j in range(i, len(s)):
        if s[j] not in node.children:
          node.children[s[j]] = TrieNode()
        node = node.children[s[j]]
        if node.isWord:
          ans = j
      return ans

    for word in words:
      insert(word)

    boldEnd = -1  # `s[i..boldEnd]` should be bolded.
    for i in range(n):
      boldEnd = max(boldEnd, find(s, i))
      bold[i] = boldEnd >= i

    # Construct the with bold tags
    i = 0
    while i < n:
      if bold[i]:
        j = i
        while j < n and bold[j]:
          j += 1
        # `s[i..j)` should be bolded.
        ans.append('<b>' + s[i:j] + '</b>')
        i = j
      else:
        ans.append(s[i])
        i += 1

    return ''.join(ans)

Approach 3: Reduce to 56. Merge Intervals

  • Time: $O(|\texttt{s}|^2 \cdot \Sigma |\texttt{words[i]}|)$
  • Space: $O(|\texttt{s}| + |\texttt{words}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
 public:
  string addBoldTag(string s, vector<string>& words) {
    string ans;
    vector<pair<int, int>> intervals;
    vector<pair<int, int>> merged;

    for (const string& word : words) {
      const int n = word.length();
      for (int i = 0; i + n <= s.length(); ++i)
        if (s.substr(i, n) == word)
          intervals.emplace_back(i, i + n);
    }

    if (intervals.empty())
      return s;

    ranges::sort(intervals);

    for (const pair<int, int>& interval : intervals)
      if (merged.empty() || merged.back().second < interval.first)
        merged.push_back(interval);
      else
        merged.back().second = max(merged.back().second, interval.second);

    int prevEnd = 0;

    for (const auto& [startIndex, endIndex] : merged) {
      ans += s.substr(prevEnd, startIndex - prevEnd);
      ans += "<b>" + s.substr(startIndex, endIndex - startIndex) + "</b>";
      prevEnd = endIndex;
    }

    if (!merged.empty())
      ans += s.substr(merged.back().second);

    return ans;
  }
};