Description#
You are given a string s and an array of strings words.
You should add a closed pair of bold tag <b> and </b> to wrap the substrings in s that exist in words.
- If two such substrings overlap, you should wrap them together with only one pair of closed bold-tag.
- If two substrings wrapped by bold tags are consecutive, you should combine them.
Return s after adding the bold tags.
Example 1:
Input: s = "abcxyz123", words = ["abc","123"]
Output: "<b>abc</b>xyz<b>123</b>"
Explanation: The two strings of words are substrings of s as following: "abcxyz123".
We add <b> before each substring and </b> after each substring.
Example 2:
Input: s = "aaabbb", words = ["aa","b"]
Output: "<b>aaabbb</b>"
Explanation:
"aa" appears as a substring two times: "aaabbb" and "aaabbb".
"b" appears as a substring three times: "aaabbb", "aaabbb", and "aaabbb".
We add <b> before each substring and </b> after each substring: "<b>a<b>a</b>a</b><b>b</b><b>b</b><b>b</b>".
Since the first two <b>'s overlap, we merge them: "<b>aaa</b><b>b</b><b>b</b><b>b</b>".
Since now the four <b>'s are consecutive, we merge them: "<b>aaabbb</b>".
Constraints:
1 <= s.length <= 10000 <= words.length <= 1001 <= words[i].length <= 1000s and words[i] consist of English letters and digits.- All the values of
words are unique.
Note: This question is the same as 758: https://leetcode.com/problems/bold-words-in-string/
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| class Trie:
def __init__(self):
self.children = [None] * 128
self.is_end = False
def insert(self, word):
node = self
for c in word:
idx = ord(c)
if node.children[idx] is None:
node.children[idx] = Trie()
node = node.children[idx]
node.is_end = True
class Solution:
def addBoldTag(self, s: str, words: List[str]) -> str:
trie = Trie()
for w in words:
trie.insert(w)
n = len(s)
pairs = []
for i in range(n):
node = trie
for j in range(i, n):
idx = ord(s[j])
if node.children[idx] is None:
break
node = node.children[idx]
if node.is_end:
pairs.append([i, j])
if not pairs:
return s
st, ed = pairs[0]
t = []
for a, b in pairs[1:]:
if ed + 1 < a:
t.append([st, ed])
st, ed = a, b
else:
ed = max(ed, b)
t.append([st, ed])
ans = []
i = j = 0
while i < n:
if j == len(t):
ans.append(s[i:])
break
st, ed = t[j]
if i < st:
ans.append(s[i:st])
ans.append('<b>')
ans.append(s[st : ed + 1])
ans.append('</b>')
j += 1
i = ed + 1
return ''.join(ans)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
| class Trie {
Trie[] children = new Trie[128];
boolean isEnd;
public void insert(String word) {
Trie node = this;
for (char c : word.toCharArray()) {
if (node.children[c] == null) {
node.children[c] = new Trie();
}
node = node.children[c];
}
node.isEnd = true;
}
}
class Solution {
public String addBoldTag(String s, String[] words) {
Trie trie = new Trie();
for (String w : words) {
trie.insert(w);
}
List<int[]> pairs = new ArrayList<>();
int n = s.length();
for (int i = 0; i < n; ++i) {
Trie node = trie;
for (int j = i; j < n; ++j) {
int idx = s.charAt(j);
if (node.children[idx] == null) {
break;
}
node = node.children[idx];
if (node.isEnd) {
pairs.add(new int[] {i, j});
}
}
}
if (pairs.isEmpty()) {
return s;
}
List<int[]> t = new ArrayList<>();
int st = pairs.get(0)[0], ed = pairs.get(0)[1];
for (int j = 1; j < pairs.size(); ++j) {
int a = pairs.get(j)[0], b = pairs.get(j)[1];
if (ed + 1 < a) {
t.add(new int[] {st, ed});
st = a;
ed = b;
} else {
ed = Math.max(ed, b);
}
}
t.add(new int[] {st, ed});
int i = 0, j = 0;
StringBuilder ans = new StringBuilder();
while (i < n) {
if (j == t.size()) {
ans.append(s.substring(i));
break;
}
st = t.get(j)[0];
ed = t.get(j)[1];
if (i < st) {
ans.append(s.substring(i, st));
}
++j;
ans.append("<b>");
ans.append(s.substring(st, ed + 1));
ans.append("</b>");
i = ed + 1;
}
return ans.toString();
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| class Trie {
public:
vector<Trie*> children;
bool isEnd;
Trie() {
children.resize(128);
isEnd = false;
}
void insert(string word) {
Trie* node = this;
for (char c : word) {
if (!node->children[c]) node->children[c] = new Trie();
node = node->children[c];
}
node->isEnd = true;
}
};
class Solution {
public:
string addBoldTag(string s, vector<string>& words) {
Trie* trie = new Trie();
for (string w : words) trie->insert(w);
int n = s.size();
vector<pair<int, int>> pairs;
for (int i = 0; i < n; ++i) {
Trie* node = trie;
for (int j = i; j < n; ++j) {
int idx = s[j];
if (!node->children[idx]) break;
node = node->children[idx];
if (node->isEnd) pairs.push_back({i, j});
}
}
if (pairs.empty()) return s;
vector<pair<int, int>> t;
int st = pairs[0].first, ed = pairs[0].second;
for (int i = 1; i < pairs.size(); ++i) {
int a = pairs[i].first, b = pairs[i].second;
if (ed + 1 < a) {
t.push_back({st, ed});
st = a, ed = b;
} else
ed = max(ed, b);
}
t.push_back({st, ed});
string ans = "";
int i = 0, j = 0;
while (i < n) {
if (j == t.size()) {
ans += s.substr(i);
break;
}
st = t[j].first, ed = t[j].second;
if (i < st) ans += s.substr(i, st - i);
ans += "<b>";
ans += s.substr(st, ed - st + 1);
ans += "</b>";
i = ed + 1;
++j;
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| type Trie struct {
children [128]*Trie
isEnd bool
}
func newTrie() *Trie {
return &Trie{}
}
func (this *Trie) insert(word string) {
node := this
for _, c := range word {
if node.children[c] == nil {
node.children[c] = newTrie()
}
node = node.children[c]
}
node.isEnd = true
}
func addBoldTag(s string, words []string) string {
trie := newTrie()
for _, w := range words {
trie.insert(w)
}
n := len(s)
var pairs [][]int
for i := range s {
node := trie
for j := i; j < n; j++ {
if node.children[s[j]] == nil {
break
}
node = node.children[s[j]]
if node.isEnd {
pairs = append(pairs, []int{i, j})
}
}
}
if len(pairs) == 0 {
return s
}
var t [][]int
st, ed := pairs[0][0], pairs[0][1]
for i := 1; i < len(pairs); i++ {
a, b := pairs[i][0], pairs[i][1]
if ed+1 < a {
t = append(t, []int{st, ed})
st, ed = a, b
} else {
ed = max(ed, b)
}
}
t = append(t, []int{st, ed})
var ans strings.Builder
i, j := 0, 0
for i < n {
if j == len(t) {
ans.WriteString(s[i:])
break
}
st, ed = t[j][0], t[j][1]
if i < st {
ans.WriteString(s[i:st])
}
ans.WriteString("<b>")
ans.WriteString(s[st : ed+1])
ans.WriteString("</b>")
i = ed + 1
j++
}
return ans.String()
}
|
