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

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

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

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;
    }
};