LeetCode Solutions

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

Space: $O(|\texttt{s}|)$

			

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

			

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

			

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)