# Leetcode: Bold Words in String

Bold Words in String

Similar Problems:

Given a set of keywords words and a string S, make all appearances of all keywords in S bold. Any letters between <b> and </b> tags become bold.

The returned string should use the least number of tags possible, and of course the tags should form a valid combination.

For example, given that words = [“ab”, “bc”] and S = “aabcd”, we should return “a<b>abc</b>d”. Note that returning “a<b>a<b>b</b>c</b>d” would use more tags, so it is incorrect.

Note:

1. words has length in range [0, 50].
2. words[i] has length in range [1, 10].
3. S has length in range [0, 500].
4. All characters in words[i] and S are lowercase letters.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

```// Blog link: https://code.dennyzhang.com/bold-words-in-string
// Basic Ideas: Merge interval
// list: marked[bool], then merge the ranges.
// Complexity: Time O(n*k), Space O(n)
//             k the total length of words
func boldWords(words []string, S string) string {
marked := make([]bool, len(S)+1)
for i, _ := range S {
end := i
for _, word := range words {
if strings.Index(S[i:], word) == 0 {
if len(word)+i > end { end = len(word)+i }
}
}
for j:=i; j<end; j++ { marked[j]=true }
}

ret, has_started := "", false
for i, ch := range S+";" {
if has_started == false && marked[i] == true {
has_started = true
ret += "<b>"
}
if has_started == true && marked[i] == false {
has_started = false
ret += "</b>"
}
if ch != ';' { ret += string(ch) }
}
return ret
}
```

Share It, If You Like It.