题目大意:给你一个字符串和一些要加粗的单词,返回加粗后的HTML代码。
Problem:
Given a set of keywords words
and a string S
, make all appearances of all keywords in S
bold. Any letters between <b>
and </b>
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 "a<b>abc</b>d"
. Note that returning "a<b>a<b>b</b>c</b>d"
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]
andS
are lowercase letters.
Solution:
C++
Time complexity: O(nL^2)
Space complexity: O(n + d)
d: size of dictionary
L: max length of the word which is 10.
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 |
// Author: Huahua // Running time: 13 ms class Solution { public: string boldWords(vector<string>& words, string S) { const int kMaxWordLen = 10; unordered_set<string> dict(words.begin(), words.end()); int n = S.length(); vector<int> bolded(n, 0); for (int i = 0; i < n; ++i) for (int l = 1; l <= min(n - i, kMaxWordLen); ++l) if (dict.count(S.substr(i, l))) std::fill(bolded.begin() + i, bolded.begin() + i + l, 1); string ans; for (int i = 0; i < n; ++i) { if (bolded[i] && (i == 0 || !bolded[i - 1])) ans += "<b>"; ans += S[i]; if (bolded[i] && (i == n - 1 || !bolded[i + 1])) ans += "</b>"; } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment