# Bold Words in String LeetCode Solution

Difficulty Level Medium

## Problem Statement

Bold Words in String LeetCode Solution – Given an array of keywords words and a string s, make all appearances of all keywords words[i] in s bold. Any letters between <b> and </b> tags become bold.

Return s after adding the bold tags. The returned string should use the least number of tags possible, and the tags should form a valid combination.

## Example

### Input:

words = [“ab”, “bc”]

s = “aabcd”

“a<b>ab</b>cd”

## Explanation

We might think returning “a<b>a<b>b</b>c</b>d” will be easy. But it would use more tags. But we need to use the least number of tags. So the correct output is “a<b>ab</b>cd”.

### Approach

Idea

1. boldMap initialize with all 0, use for mark bold char.
2. Go through each word and mark it in boldMap.
3. loop through string S and use openTag to check if we should open or close the tag.
4. In the end, if the tag is still open, we should close it.

## Code for Bold Words in String LeetCode Solution

### Java Program

class Solution {
public String boldWords(String[] words, String s) {
boolean[] bold = new boolean[s.length() + 1];
for(String w : words)
for(int i = s.indexOf(w); i != -1; i = s.indexOf(w, i + 1))
Arrays.fill(bold, i, i + w.length(), true);
StringBuilder r = new StringBuilder(bold[0] ? "<b>" : "");
for(int i = 0; i < bold.length - 1; i++){
r.append(s.charAt(i));
r.append(bold[i] && !bold[i + 1] ? "</b>" : "");
r.append(!bold[i] && bold[i + 1] ? "<b>" : "");
}
return r.toString();
}
}

### C++ Program

class Solution {
public:
string boldWords(vector<string>& words, string S) {
vector<bool> bold(S.size(), false);
for(int i=0;i<words.size();i++) {
for(int j=0;j+words[i].size()<=S.size();j++) {
if(S.substr(j, words[i].size())!=words[i]) continue;
for(int k=0;k<words[i].size();k++) bold[j+k]=true;
}
}
string res;
if(bold[0]) res+="<b>";
for(int i=0;i<S.size();i++) {
res.append(1, S[i]);
if(i==S.size()-1) break;
if(!bold[i]&&bold[i+1]) res+="<b>";
else if(bold[i]&&!bold[i+1]) res+="</b>";
}
if(bold.back()) res+="</b>";
return res;
}
};

## Complexity Analysis for Bold Words in String LeetCode Solution

Let N be the length of the input string.

Time complexity: O(N)

We are only iterating over the input string. So it will take O(N) time.

Space complexity: O(N)

We are storing the string in an array. So it will take O(N) space.

Translate »