【LeetCode】758. Bold Words in String 解题报告(C++)

作者：负雪明烛
id： fuxuemingzhu
个人博客：http://fuxuemingzhu.cn/

题目描述

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.

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

For example, 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:

words has length in range [0, 50].
words[i] has length in range [1, 10].
S has length in range [0, 500].
All characters in words[i] and S are lowercase letters.

题目大意

给定一个关键词集合 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;

    }

};

日期

2019 年 9 月 18 日 —— 今日又是九一八

巴特西

【LeetCode】758. Bold Words in String 解题报告(C++)

目录

题目描述

题目大意

解题方法

遍历

日期

最新文章

热门文章