758. Bold Words in String 字符串中的加粗单词

题目地址：https://leetcode-cn.com/problems/bold-words-in-string/

题目描述

Given a set of keywords words and a string S, make all appearances of all keywords in S bold. Any letters between  and  tags become bold.

Thereturned string should use the least number of tags possible, and of course the tags should form a valid combination.

Forexample, given that words = ["ab", "bc"] and S = "aabcd", we should return "aabcd". Note that returning "aabcd" would use more tags, so it is incorrect.

Note:

1、 wordshaslengthinrange[0,50].；
2、 words[i]haslengthinrange[1,10].；
3、 Shaslengthinrange[0,500].；
4、 Allcharactersinwords[i]andSarelowercaseletters.；

题目大意

给定一个关键词集合 words 和一个字符串 S，将所有 S 中出现的关键词加粗。所有在标签  和  中的字母都会加粗。返回的字符串需要使用尽可能少的标签，当然标签应形成有效的组合。例如，给定 words = ["ab", "bc"] 和 S = "aabcd"，需要返回 "aabcd"。注意返回 "aabcd" 会使用更多的标签，因此是错误的。

解题方法

遍历

先使用一个数组isBold保存S中的每个字符是否应该加粗，判断的方式是，遍历words中的每个字符串，找出S中有哪些位置和它匹配。

是否增加标签的方法是当前字符需要加粗，但是其前面的字符不用加粗，或者当前字符是第一个字符。是否增加标签的方法是当前字符需要加粗，但是其后面的字符不用加粗，或者当前字符是最后一个字符。

C++代码如下：

class Solution {
public:
    string boldWords(vector<string>& words, string S) {
        const int N = S.size();
        vector<bool> isBold(N, false);
        for (string& word : words) {
            for (int i = 0; i < N; ++i) {
                string sub = S.substr(i, word.size());
                if (sub == word) {
                    for (int k = i; k < i + word.size(); ++k) {
                        isBold[k] = true;
                    }
                }
            }
        }
        string res;
        for (int i = 0; i < N; ++i) {
            if (isBold[i] && (i == 0 || !isBold[i - 1])) {
                res += "<b>";
            }
            res += S[i];
            if (isBold[i] && (i == N - 1 || !isBold[i + 1])) {
                res += "</b>";
            }
        }
        return res;
    }
};

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

2022

DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有

本文经作者：负雪明烛授权发布，任何组织或个人未经作者授权不得转发