内容简介:[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:
- 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].
题目大意:
给定字符串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
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
以匠心,致设计:网易 UEDC 用户体验设计
网易用户体验设计中心 / 电子工业出版社 / 2018-8 / 95.00元
为什么网易云音乐的体验流畅细腻、富有温度?为什么网易严选App的UI设计让人感到温馨、舒适?为什么网易蜗牛读书App的界面设计让用户爱不释手…… 《以匠心,致设计:网易 UEDC 用户体验设计》是网易用户体验设计团队对自身过去的设计思考的精心总结,最大程度还原了网易产品背后的设计故事,内容涵盖设计基础、设计实践、方法思考、成长指南四章,借助网易产品设计的实际案例具体讲述了设计师日常工作中不可......一起来看看 《以匠心,致设计:网易 UEDC 用户体验设计》 这本书的介绍吧!