Problem

In the given problem we are given a string s and a list of substrings dict and we need to surround all substrings (exists in dict) in s with the bold tag <b> and </b>. If two substrings are overlapping or are consecutive in s then wrap them together with one pair of bold tag.

Consider the following example:

Example

Input :

s = "abcxyz123" dict = ["abc","123"]

Output:

"abcxyz123"

The string contains "abc" and "123" and both are in the dict so they are wrapped by <b> and </b>.

Approach

To solve the problem, we create a boolean array bold, where bold[i] is true if s[i] is within one of the strings in dict else false. This can be done by finding the maximum end index end for each string where end = start + len(string).

Then, whenever we find a block in the string that starts and ends with bold tag, we wrap that block with <b> and </b>.

Python Solution

This is a Python solution using the approach described earlier:

1
2python
3class Solution:
4    def addBoldTag(self, s: str, words: List[str]) -> str:
5        lookup = [0]*len(s)  # initialize bold array with 0's
6        for word in words:  # for string in dict
7            start = s.find(word)  
8            while start != -1:  # for overlapping and consecutive strings
9                lookup[start:start+len(word)] = [1]*len(word)
10                start = s.find(word,start+1)
11        res = ""
12        for i in range(len(s)):
13            if lookup[i] and (i==0 or lookup[i-1] ==0):  # add starting tag
14                res += "<b>"
15            res += s[i]
16            if lookup[i] and (i==len(s)-1 or lookup[i+1] == 0):  # add closing tag
17                res += "</b>"
18        return res

JAVA Solution

This is a Java solution using an approach similar to the one discussed above.

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

JavaScript Solution

This is JavaScript solution using the approach discussed above.

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

C# Solution

This is a C# solution using a similar approach to that described earlier.

1
2C#
3public class Solution {
4    public string AddBoldTag(string s, string[] dict) {
5        int[] bold = new int[s.Length];
6        foreach (var word in dict) {
7            int start = s.IndexOf(word);
8            while (start != -1) {
9                int end = start + word.Length;
10                for (int i = start; i < end; i++)
11                    bold[i] = 1;
12                start = s.IndexOf(word, start + 1);
13            }
14        }
15        StringBuilder res = new StringBuilder();
16        for (int i = 0; i < s.Length; i++) {
17            if (bold[i]==1 && (i == 0 || bold[i - 1] == 0))
18                res.Append("<b>");
19            res.Append(s[i]);
20            if (bold[i]==1 && (i == s.Length - 1 || bold[i + 1] == 0))
21                res.Append("</b>");
22        }
23        return res.ToString();
24    }
25}

C++ Solution

This is a C++ solution using a similar approach to that described earlier.

1
2C++
3class Solution {
4public:
5    string addBoldTag(string s, vector<string>& dict) {
6        vector<bool> bold(s.length(), false);
7        for (string word : dict) {
8            size_t start = s.find(word);
9            while (start != string::npos) {
10                for (int i = start; i < start + word.length(); i++)
11                    bold[i] = true;
12                start = s.find(word, start + 1);
13            }
14        }
15        string res = "";
16        for (int i = 0; i < s.length(); i++) {
17            if (bold[i] && (i==0 || !bold[i - 1])) res += "<b>";
18            res += s[i];
19            if (bold[i] && (i==s.length()-1 || !bold[i + 1])) res += "</b>";
20        }
21        return res;
22    }
23};

Note: In all the above languages ==1/==0 and true/false are interchangeable.

The solution above iterate over the string and insert the bold tags where appropriate. The techniques used in this solution are string manipulation and traversing arrays.# PHP Solution This is a PHP solution using a similar approach to the one discussed earlier.

1
2php
3function addBoldTag($s, $dict) {
4    $bold = array_fill(0, strlen($s), false); 
5    foreach ($dict as $word) { 
6        $start = strpos($s, $word);  
7        while ($start !== false) { 
8            array_splice($bold, $start, strlen($word), array_fill($start, strlen($word), true));
9            $start = strpos($s, $word, $start + 1);
10        }
11    }
12    $res = "";
13    for ($i = 0; $i < strlen($s); $i++) {
14        if ($bold[$i] && ($i === 0 || !$bold[$i - 1])) {
15            $res .= "<b>";
16        }
17        $res .= $s[$i];
18        if ($bold[$i] && ($i === strlen($s) - 1 || !$bold[$i + 1])) {
19            $res .= "</b>";
20        }
21    }
22    return $res;
23}

In the PHP solution, an array of booleans is created to track the characters in the string that should be bolded. The PHP functions array_fill and array_splice are used to mark the appropriate characters in the bold array. The substrings are then inserted, surrounded by bold tags, into the result string.

Go Solution

This is a Go solution using a similar approach to that described earlier.

1
2go
3func addBoldTag(s string, dict []string) string {
4    bold := make([]bool, len(s))
5    for _, word := range dict {
6         start := strings.Index(s, word)
7         for start != -1 {
8             for i := start; i < start+len(word); i++ {
9                 bold[i] = true
10             }
11             start = strings.Index(s[start+len(word):], word)
12         }
13    }
14    res := ""
15    for i := 0; i < len(s); i++ {
16         if bold[i] && (i == 0 || !bold[i-1]) {
17             res += "<b>"
18         }
19         res += string(s[i])
20         if bold[i] && (i == len(s)-1 || !bold[i+1]) {
21             res += "</b>"
22         }
23    }
24    return res
25}

The Go solution makes use of Go's make built-in function to create a slice of booleans. It uses the strings.Index function to find the start index of each word in s and then marks the characters from start to start+len(word) as true in the bold slice.

Conclusion

In conclusion, the above solutions demonstrate how to surround all substrings (exists in dict) in a string s with the bold tag <b> and </b> using multiple programming languages. The same data structures and algorithms are used based on the language syntax. They all create a boolean array bold and initialize it, then use a for loop and while loop to find the maximum end index for each string in dict. After that, it utilizes another for loop to wrap the block with <b> and </b>.

The solutions are implemented in Python, Java, JavaScript, C#, C++, PHP and Go, showcasing how the problem can be solved in multiple languages.