Leetcode 616. Add Bold Tag in String
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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.