Add Bold Tag in String

https://leetcode.com/problems/add-bold-tag-in-string/description/

Given a string s and a list of strings dict, you need to add a closed pair of bold tag <b> and </b> to wrap the substrings in s that exist in dict. If two such substrings overlap, you need to wrap them together by only one pair of closed bold tag. Also, if two substrings wrapped by bold tags are consecutive, you need to combine them.

Example 1:

Input:

s = "abcxyz123"

dict = ["abc","123"]

Output:

"<b>abc</b>xyz<b>123</b>"

Example 2:

Input:

s = "aaabbcc"

dict = ["aaa","aab","bc"]

Output:

"<b>aaabbc</b>c"

Note:

The given dict won't contain duplicates, and its length won't exceed 100.

All the strings in input have length in range [1, 1000].

Thoughts

让end表示bold结束位置. 对s遍历, 依次判断i开始的substring能否构成word中某个词, 能则把i + 这个词长度和当前end比较, 长则代表bold长度end可以继续更新.

Code

class Solution {
    public String addBoldTag(String s, String[] dict) {
        StringBuilder sb = new StringBuilder();
        boolean tag = false;
        for (int i = 0, end = 0; i < s.length(); i++) {
            for (String word : dict) {
                if (s.startsWith(word, i)) {
                    end = Math.max(end, i + word.length());
                }
            }
            if (end > i) {
                if (!tag) {
                    sb.append("<b>");
                }
                tag = true;
            } else {
                if (tag) {
                    sb.append("</b>");
                }
                tag = false;
            }
            sb.append(s.charAt(i));
        }
        if (tag) {
            sb.append("</b>");
        }
        return sb.toString();
    }
}

Analysis

时间复杂度O(MN), M为s长度, N为dict所有字符长度.