​LeetCode刷题实战615:给字符串添加加粗标签

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 给字符串添加加粗标签,我们先来看题面:
https://leetcode.cn/problems/add-bold-tag-in-string/
​LeetCode刷题实战615:给字符串添加加粗标签

给一个字符串 s 和一个字符串列表 dict ,你需要将在字符串列表中出现过的 s 的子串添加加粗闭合标签 和 。如果两个子串有重叠部分,你需要把它们一起用一个闭合标签包围起来。同理,如果两个子字符串连续被加粗,那么你也需要把它们合起来用一个加粗标签包围。

样例 1:


输入:
s = “abcxyz123”
dict = [“abc”,“123”]
输出:
“abcxyz123”


样例 2:

输入:
s = “aaabbcc”
dict = [“aaa”,“aab”,“bc”]
输出:
“aaabbcc”

注意:
给定的 dict 中不会有重复的字符串,且字符串数目不会超过 100 。
输入中的所有字符串长度都在范围 [1, 1000] 内。


解题

https://blog.csdn.net/weixin_44171872/article/details/108982935

主要思路:
(1)先将字典中的各个单词在字符串中的可能出现的位置进行标识;
(2)然后根据标识的位置,在字符串中出入标签;


class Solution {
public:
    string addBoldTag(string s, vector<string>& dict) {
      //标识出现过的单词
        vector<bool> sign(s.size(),false);
        //将字典中的各个单词在字符串中标识
        for(string& word:dict){//当前要处理的单词
          //字符串中的各个位置
            int pos=0;
            //遍历字符串的结尾
            int end_pos=s.size()-word.size()+1;
            while(pos<end_pos){
                if(s[pos]==word[0]){
                    int k=0;
                    //判断当前单词是否在字符串的当前位置
                    while(k<word.size()){
                        if(s[pos+k]!=word[k]){
                            break;
                        }
                        ++k;
                    }
                    //若在,则对单词进行标识
                    if(k==word.size()){
                        k=0;
                        while(k<word.size()){
                            sign[pos+k]=true;
                            ++k;
                        }
                    }
                }
                //字符串中的下一个单词
                ++pos;
            }
        }
    //根据标识,插入标签
        int pos=0;
        string res;
        while(pos<s.size()){
          //若此位置开始,有单词出现
            if(sign[pos]){
                res+="<b>";//插入标签前面部分
                //压入出现过单词的部分
                while(pos<s.size()&&sign[pos]){
                    res.push_back(s[pos]);
                    ++pos;
                }
                //插入标签的后面部分
                res+="</b>";
            }
            else{//将非出现单词的部分直接压入结果中
                res.push_back(s[pos]);
                ++pos;
            }
        }
        return res;
    }
};


上期推文:
LeetCode1-600题汇总,希望对你有点帮助!
LeetCode刷题实战601:体育馆的人流量
LeetCode刷题实战602:好友申请 II :谁有最多的好友
LeetCode刷题实战603:连续空余座位
LeetCode刷题实战604:迭代压缩字符串
LeetCode刷题实战605:种花问题
LeetCode刷题实战606:根据二叉树创建字符串
LeetCode刷题实战607:销售员
LeetCode刷题实战608:树节点
LeetCode刷题实战609:在系统中查找重复文件
LeetCode刷题实战610:判断三角形
LeetCode刷题实战611:有效三角形的个数
LeetCode刷题实战612:平面上的最近距离
LeetCode刷题实战613:直线上的最近距离
LeetCode刷题实战614:二级关注者
LeetCode刷题实战615:平均工资:部门与公司比较

​LeetCode刷题实战615:给字符串添加加粗标签

本篇文章来源于微信公众号:程序IT圈

原创文章,作者:栈长,如若转载,请注明出处:https://www.cxyquan.com/23408.html

发表评论

登录后才能评论

联系我们

400-800-8888

在线咨询:点击这里给我发消息

邮件:admin@example.com

工作时间:周一至周五,9:30-18:30,节假日休息