文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給定一個關鍵詞集合 words 和一個字符串 S，將所有 S 中出現的關鍵詞加粗。所有在標簽 <b> 和 </b> 中的字母都會加粗。

返回的字符串需要使用盡可能少的標簽，當然標簽應形成有效的組合。

例如，給定 words = ["ab", "bc"] 和 S = "aabcd"，需要返回 "a<b>abc</b>d"。注意返回 "a<b>a<b>b</b>c</b>d" 會使用更多的標簽，因此是錯誤的。

注： words 長度的范圍為 [0, 50]。 words[i] 長度的范圍為 [1, 10]。 S 長度的范圍為 [0, 500]。 所有 words[i] 和 S 中的字符都為小寫字母。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/bold-words-in-string
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

同樣題目：LeetCode 616. 給字符串添加加粗標簽（Trie樹）

• 將集合里的單詞全部插入trie樹
• 以S的每個位置為起點在trie樹開始查找完整單詞，記錄可以加黑的地方，標記在bool數組里

class trie { public:trie* next[26] = {NULL};bool isend = false;int count = 0;void insert(string& s){trie* cur = this;for(int i = 0; i < s.size(); i++){if(cur->next[s[i]-'a'] == NULL)cur->next[s[i]-'a'] = new trie();cur = cur->next[s[i]-'a'];}cur->count++;cur->isend = true;} }; class Solution { public:string boldWords(vector<string>& words, string S) {trie *t = new trie(), *cur;for(auto& w : words)t->insert(w);vector<bool> bold(S.size(), false);//加黑標記int boldl = 0, boldr=-1;//開始加粗的位置l,rfor(int i = 0, j; i < S.size(); ++i){cur = t;boldl = max(boldl, i);//加黑的地方左端點j = i;while(j < S.size() && cur && cur->next[S[j]-'a']){cur = cur->next[S[j]-'a'];if(cur->isend)boldr = j;//可以加黑的右端點j++;}while(boldl <= boldr)bold[boldl++] = true;//標記加黑}string ans;for(int i = 0; i < S.size(); ++i){if((i==0 && bold[i]) || (i>0 && !bold[i-1] && bold[i]))//i起點ans += "<b>";ans += S[i];if((i==S.size()-1 && bold[i]) || (i<S.size()-1 && bold[i] && !bold[i+1]))//i是終點ans += "</b>";}return ans;} };

12 ms 11.2 MB

---

長按或掃碼關注我的公眾號，一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 758. 字符串中的加粗单词（Trie树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。