Trie
Array
Hash Table
String
String Matching
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: "abc xyz123 ".
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: "aa abbb" and "aaa bbb".
"b" appears as a substring three times: "aaab bb", "aaabb b", 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 <= 1000
0 <= words.length <= 100
1 <= words[i].length <= 1000
s
and words[i]
consist of English letters and digits.
All the values of words
are unique .
Note: This question is the same as 758. Bold Words in String .
Solutions
Solution 1
Python3 Java C++ Go
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 ()
}