[LeetCode]Add Bold Tag in String

内容简介：[LeetCode]Add Bold Tag in String

题目描述：

LeetCode 616. Add Bold Tag in String

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:

1. The given dict won't contain duplicates, and its length won't exceed 100.
2. All the strings in input have length in range [1, 1000].

题目大意：

给定字符串s和一组字符串dict，在s中寻找在dict中出现过的子串，并在其首位添加加粗标签。

如果两个子串相互重叠或者首位相连，将加粗标签进行合并。

解题思路：

朴素解法

时间复杂度O(n * m)，其中n为s的长度，m为dict中字符串长度之和

变量start， end记录当前需要加粗标记的子串起止下标，初始为-1

在s中枚举子串起点x，记当前字符为c

遍历dict，寻找与s[x:]匹配长度最长的子串，记其长度为nend

    若nend > 0：
    
        若start为-1，将其设为x
        
        将end更新为其与nend + x的较大值
    
    否则：
    
         若 x >= end > 0：将<b> + s[start:end] + </b>累加至答案，并将start与end重置为-1
         
         若start == -1：将c累加至答案

若start > -1：将<b> + s[start:end] + </b>累加至答案

Python代码：

class Solution(object):
    def addBoldTag(self, s, dict):
        """
        :type s: str
        :type dict: List[str]
        :rtype: str
        """
        start = end = -1
        ans = ''
        for x, c in enumerate(s):
            nend = 0
            for d in dict:
                if s[x:].startswith(d):
                    nend = max(nend, len(d))
            if nend:
                if start == -1: start = x
                end = max(end, nend + x)
                continue
            if x >= end:
                ans += '<b>' + s[start:end] + '</b>'
                start = end = -1
            if start == -1: ans += c
        if start > -1: ans += '<b>' + s[start:end] + '</b>'
        return ans

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网

查看所有标签

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。