Leetcode

Add Bold Tag in String

May 26, 2022 by aAshish

Approach 1: Bold boolean array

  • Time:O(|\texttt{s}|^2 \cdot \Sigma |\texttt{words[i]}|)
  • Space:O(|\texttt{s}|)

C++

 
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 auto& 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 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;
  }
};

JAVA

 
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 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();
  }
}

Python

 
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}|)

C++

 
struct TrieNode {
  vector<TrieNode*> children;
  bool isWord = false;
  TrieNode() : children(128) {}
  ~TrieNode() {
    for (TrieNode* child : children)
      delete child;
  }
};

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 auto& 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 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:
  TrieNode root;

  void insert(const string& word) {
    TrieNode* node = &root;
    for (const char c : word) {
      if (!node->children[c])
        node->children[c] = new TrieNode;
      node = node->children[c];
    }
    node->isWord = true;
  }

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

JAVA

 
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 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;
  }
}

Python

 
class TrieNode:
  def __init__(self):
    self.children: Dict[str, TrieNode] = defaultdict(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:
        if c not in node.children:
          node.children[c] = TrieNode()
        node = node.children[c]
      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}|)

C++

 
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;

    sort(begin(intervals), end(intervals));

    for (const auto& 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;
  }
};