做企业手机网站,电子商城平台网站开发,工地找活app排行榜,河北企业建网站文章目录1. 题目2. 解题1. 题目
给定一个关键词集合 words 和一个字符串 S#xff0c;将所有 S 中出现的关键词加粗。所有在标签 b 和 /b 中的字母都会加粗。
返回的字符串需要使用尽可能少的标签#xff0c;当然标签应形成有效的组合。
例如#xff0c;…
文章目录1. 题目2. 解题1. 题目
给定一个关键词集合 words 和一个字符串 S将所有 S 中出现的关键词加粗。所有在标签 b 和 /b 中的字母都会加粗。
返回的字符串需要使用尽可能少的标签当然标签应形成有效的组合。
例如给定 words [ab, bc] 和 S aabcd需要返回 ababc/bd。注意返回 ababb/bc/bd 会使用更多的标签因此是错误的。
注
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(vectorstring words, string S) {trie *t new trie(), *cur;for(auto w : words)t-insert(w);vectorbool 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((i0 bold[i]) || (i0 !bold[i-1] bold[i]))//i起点ans b;ans S[i];if((iS.size()-1 bold[i]) || (iS.size()-1 bold[i] !bold[i1]))//i是终点ans /b;}return ans;}
};12 ms 11.2 MB 长按或扫码关注我的公众号一起加油、一起学习进步
