758. Bold Words in String
Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 1
Acceptance rate: 47.5%
Problem Breakdown
The problem requires us to make all appearances of given keywords in a string bold by wrapping them with <b> and </b> tags. The goal is to use the least number of tags possible while ensuring that the tags form a valid combination.
Inputs:
- A list of keywords
wordswhere each keyword is a string. - A string
Swhich contains lowercase letters.
Outputs:
- A modified version of
Swith all occurrences of any keyword inwordsbolded.
Implicit Constraints or Tricky Edge Cases:
- If
wordsis empty, the original stringSshould be returned unchanged. - If
Sis empty, the result should also be an empty string. - Keywords can overlap, and we need to ensure that overlapping keywords are handled correctly by using the minimum number of tags.
Intuition
A brute-force approach would involve checking every substring of S against each keyword in words and marking the positions where a keyword appears. This would result in a high time complexity due to the nested loops over all substrings and keywords.
The key insight is to use an array to mark the start and end positions of bold tags. By iterating through S, we can identify the ranges where any keyword starts or ends, and then merge these ranges to minimize the number of tags used. This approach reduces the complexity by avoiding unnecessary nested loops.
Approach
- Initialize a Marking Array: Create an array
markof length equal to the length ofS. Each element in this array will be set to 1 if it is part of any keyword, otherwise 0. - Mark Positions: For each word in
words, iterate throughSand mark the positions where the word starts as 1 in themarkarray. - Merge Ranges: Iterate through the
markarray to identify contiguous ranges of 1s. These ranges represent the substrings that need to be bolded. - Construct Result String: Build the result string by appending characters from
Sand adding<b>and</b>tags where necessary based on the identified ranges.
Complexity Analysis
- Time Complexity: O(n * m), where n is the length of
Sand m is the total number of characters in all keywords combined. This is because we iterate throughSfor each keyword. - Space Complexity: O(n) for storing the
markarray and the result string.
Solution
def boldWords(words, S):
n = len(S)
mark = [0] * n
# Mark positions in 'mark' where keywords appear
for word in words:
start = 0
while start < n:
pos = S.find(word, start)
if pos == -1:
break
for i in range(pos, pos + len(word)):
mark[i] = 1
start = pos + 1
# Construct the result string with bold tags
ans = []
i = 0
while i < n:
if mark[i] == 1:
ans.append("<b>")
while i < n and mark[i] == 1:
ans.append(S[i])
i += 1
ans.append("</b>")
else:
ans.append(S[i])
i += 1
return ''.join(ans)
Edge Cases Handled
- Empty
words: The function returns the original stringSunchanged. - Empty
S: The function returns an empty string. - Overlapping Keywords: The function correctly merges overlapping ranges to use the minimum number of tags.
The solution provided is correct, efficient, and clear. It handles all edge cases as described in the problem breakdown.