Leetcode 758. Bold Words in String

Problem

Given a set of keywords and a string S, the task is to bold all appearances of all keywords in S. Any letter encased within <b> and </b> tags is considered as bold. The returned string should use the least number of tags possible, and tags should form a valid combination.

If words = ["ab", "bc"] and S = "aabcd" we should return "a<b>abc</b>d". Returning "a<b>a<b>b</b>c</b>d" would use more tags which is incorrect as per the problem statement.

Constraints

• words has a length in the range [0, 50].
• words[i] has length in the range [1, 10].
• S has length in the range [0, 500].
• All characters in words[i] and S are lowercase letters.

Example Walkthrough

Let's walk through an example to understand the problem.

Taking the input we described earlier i.e., words = ["ab", "bc"] and S = "aabcd".

S = "aabcd"

Check every keyword in the given words if it exists in S or not.

keyword ab exists in a substring that starts at index 1. keyword bc exists in a substring that starts at index 2.

Mark these indexes and build another string with substrings using the least number of tags possible.

s = "a<b>abc</b>d"

Solution Approach

We solve this problem through a two-step process:

1. First, we process all words w in the word list and mark their end indices in the string. In this way, we know, at index i, whether it should be bold or not. This step is done iterating the given words and marking our bold array whenever we find a word in our string.

2. Then, going through the strings from left to right, we open a tag when the first change from non-bold to bold, close it when the first change from bold to non-bold.

Python Solution

Below is the solution in Python that follows the aforementioned steps:

1
2python
3class Solution:
4    def boldWords(self, words: List[str], S: str) -> str:
5        bold = [0]*len(S)
6        for word in words:
7            pos = S.find(word)
8            while pos != -1:
9                bold[pos:pos+len(word)] = [1]*len(word)
10                pos = S.find(word, pos + 1)
11                
12        result = []
13        for i in range(len(S)):
14            if bold[i] and (i == 0 or not bold[i-1]):
15                result.append("<b>")
16            result.append(S[i])
17            if bold[i] and (i == len(S)-1 or not bold[i+1]):
18                result.append("</b>")
19                
20        return ''.join(result)

In this python solution, we iterate the words array to mark the indexes in the bold array. After marking our bold array, we iterate over our string S and whenever we find an index which should be bold and wasn't previously bold, we add a <b> before it. Similarly whenever we find an index which was previously bold and then is followed by a non-bold index, we add a </b> after it. Then we join the elements in our result array and return the final result string.JavaScript Solution

The same approach can be implemented in JavaScript as well. Below is the JavaScript version of the same solution.

1
2javascript
3var boldWords = function(words, S) {
4    let bold = new Array(S.length).fill(0);
5    for(let word of words){
6        let pos = S.indexOf(word);
7        while(pos !== -1){
8            for(let i = pos; i < pos + word.length; i++){
9                bold[i] = 1;
10            }
11            pos = S.indexOf(word, pos+1);
12        }
13    }
14    let result = "";
15    for(let i=0; i<S.length; i++){
16        if(bold[i] && (i === 0 || !bold[i-1])){
17            result += "<b>";
18        }
19        result += S[i];
20        if(bold[i] && (i === S.length-1 || !bold[i+1])){
21            result += "</b>";
22        }
23    }
24
25    return result;
26}

In the JavaScript version, we again start by creating the bold array and filling it with zeroes. Then we iterate over the words array and for each word, we find all its occurrences in S and update the bold array. After marking all bold indexes, we iterate over our string S and for each index, if it needs to be bold and the previous index is not bold, we add a <b> , and vice versa we add </b>. Finally, we return the result string.

Java Solution

We can also solve the problem by using Java. Below is the Java version of the same solution.

1
2java
3class Solution {
4    public String boldWords(String[] words, String S) {
5        boolean[] bold = new boolean[S.length()];
6        for(String word : words){
7            int pos = S.indexOf(word);
8            while(pos != -1){
9                for(int i = pos; i < pos + word.length(); i++){
10                    bold[i] = true;
11                }
12                pos = S.indexOf(word, pos+1);
13            }
14        }
15        
16        StringBuilder result = new StringBuilder();
17        for(int i = 0; i < S.length(); i++){
18            if(bold[i] && (i == 0 || !bold[i-1])){
19                result.append("<b>");
20            }
21            result.append(S.charAt(i));
22            if(bold[i] && (i == S.length()-1 || !bold[i+1])){
23                result.append("</b>");
24            }
25        }
26
27        return result.toString();
28    }
29}

In the Java version, the same approach is taken. We start by creating bold boolean array and initializing all elements to false. We then iterate over all words in the words array, and for each word, we find all the appearances in String S and mark those indexes bold. After that, we iterate through our string S using a StringBuilder to build the result string and finally return the result string.