758. Bold Words in String

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

Given an array of keywords words and a string s, make all appearances of all keywords words[i] in s bold. Any letters between and tags become bold.

Return s after adding the bold tags. The returned string should use the least number of tags possible, and the tags should form a valid combination.

Example 1:

Input: words = ["ab","bc"], s = "aabcd"
Output: "a<b>abc</b>d"
Explanation: Note that returning "a<b>a<b>b</b>c</b>d" would use more tags, so it is incorrect.

Example 2:

Input: words = ["ab","cb"], s = "aabcd"
Output: "a<b>ab</b>cd"

Constraints:

• 1 <= s.length <= 500
• 0 <= words.length <= 50
• 1 <= words[i].length <= 10
• s and words[i] consist of lowercase English letters.

Note: This question is the same as 616: https://leetcode.com/problems/add-bold-tag-in-string/

Code

重复题目 616. Add Bold Tag in String

class Solution {
    public String boldWords(String[] words, String s) {
        boolean[] bold = new boolean[s.length()];
        int boldEnd = 0;

        for (int i = 0; i < s.length(); i++) {
            for (String word : words) {
                if (s.startsWith(word, i)) {
                    boldEnd = Math.max(boldEnd, i + word.length());
                }
            }

            bold[i] = boldEnd > i;
        }

        StringBuilder res = new StringBuilder();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (!bold[i]) {
                res.append(c);
                continue;
            }

            // first bold
            if(i == 0 || !bold[i - 1]) {
                res.append("<b>");
            }
            res.append(c);
            // last bold
            if(i == s.length() - 1 || !bold[i + 1]) {
                res.append("</b>");
            }
        }

        return res.toString();
    }
}