# 758. Bold Words in String

• 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 boldWords(vector& words, string s) { const int n = s.length(); string ans; // bold[i] := true if s[i] should be bolded vector 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) boldEnd = max(boldEnd, i + static_cast(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 += "" + s.substr(i, j - i) + ""; 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 boldWords(String[] words, String s) { 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("").append(s.substring(i, j)).append(""); 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 boldWords(self, words: List[str], s: 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 string with the 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('' + s[i:j] + '') i = j else: ans.append(s[i]) i += 1 return ''.join(ans)