给定一个关键词集合 words 和一个字符串 s，将所有 s 中出现的关键词 words[i] 加粗。所有在标签 <b> 和 <b> 中的字母都会加粗。
加粗后返回 s 。返回的字符串需要使用尽可能少的标签，当然标签应形成有效的组合。
示例 1:
输入: words = ["ab","bc"], s = "aabcd"
输出: "a<b>abc</b>d"
解释: 注意返回 "a<b>a<b>b</b>c</b>d" 会使用更多的标签，因此是错误的。
示例 2:
输入: words = ["ab","cb"], s = "aabcd" 输出: "a<b>ab</b>cd"
提示:
1 <= s.length <= 5000 <= words.length <= 501 <= words[i].length <= 10s和words[i]由小写英文字母组成
注：此题与「616 - 给字符串添加加粗标签」相同 - https://leetcode.cn/problems/add-bold-tag-in-string/
方法一：前缀树 + 区间合并
相似题目：1065. 字符串的索引对、616. 给字符串添加加粗标签
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 boldWords(self, words: List[str], s: 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)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 boldWords(String[] words, String s) {
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();
}
}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 boldWords(vector<string>& words, string s) {
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;
}
};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 boldWords(words []string, s 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()
}