前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LWC 66: 758. Bold Words in String

LWC 66: 758. Bold Words in String

作者头像
用户1147447
发布2019-05-26 09:23:35
3800
发布2019-05-26 09:23:35
举报
文章被收录于专栏:机器学习入门机器学习入门

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434636

LWC 66: 758. Bold Words in String

传送门:758. Bold Words in String

Problem:

Given a set of keywords words and a string S, make all appearances of all keywords in S bold. Any letters between and 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 “aabcd”. Note that returning “aabcd” would use more tags, so it is incorrect.

Note:

  • words has length in range 0, 50.
  • wordsi has length in range 1, 10.
  • S has length in range 0, 500.
  • All characters in wordsi and S are lowercase letters.

思路:

S的长度不长,所以可以用一个boolean数组记录每个位置是否需要加粗。起初,我for循环两次S,得到可能的subString判断是否在words中存在,结果超时了,解决超时的关键在于note,words的长度最多就10,所以干脆从可能的word中找是否有对应S的subString,这样即解决了超时。

Java版本如下:

代码语言:javascript
复制
    public String boldWords(String[] words, String S) {
        int n = S.length();
        boolean[] marked = new boolean[n];
        for (int i = 0; i < n; ++i) {
            for (String word : words) {
                if (i + word.length() <= n && word.equals(S.substring(i, i + word.length()))) {
                    for (int j = i; j < i + word.length(); ++j) {
                        marked[j] = true;
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        int j = 0;
        while (j < n) {
            while (j < n && !marked[j]) {
                sb.append(S.charAt(j));
                j ++;
            }
            if (j >= n) break;
            StringBuilder tmp = new StringBuilder();
            while (j < n && marked[j]) {
                tmp.append(S.charAt(j));
                j ++;
            }
            if (tmp.length() != 0) sb.append("<b>" + tmp.toString() + "</b>");
        }
        return sb.toString();
    }

不过我们还可以采用IMOS累积法,这样可以省去一个for循环。

Java代码如下:

代码语言:javascript
复制
    public String boldWords(String[] words, String S) {
        int n = S.length();
        int[] hits = new int[n];
        for (int i = 0; i < n; ++i) {
            for (String word : words) {
                if (i + word.length() <= n && word.equals(S.substring(i, i + word.length()))) {
                    hits[i] ++;
                    hits[i + word.length()] --;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i < n; ++i) hits[i] += hits[i - 1];
        for (int i = 0; i < n; ++i) {
            if (hits[i] > 0) {
                sb.append("<b>" + S.charAt(i) + "</b>");
            }
            else sb.append(S.charAt(i));
        }
        return sb.toString().replace("</b><b>", "");
    }

Python版本:

代码语言:javascript
复制
class Solution(object):
    def boldWords(self, words, S):
        """
        :type words: List[str]
        :type S: str
        :rtype: str
        """
        n = len(S)
        hits = [0] * (n + 1)
        for i in range(n):
            for word in words:
                if (i + len(word) <= n and word == S[i:i + len(word)]):
                    hits[i] += 1
                    hits[i + len(word)] -= 1
        for i in range(1, n + 1): hits[i] += hits[i - 1]
        ans = ""
        i = 0;
        while (i < n):
            while (i < n and hits[i] == 0):
                ans += S[i]
                i += 1
            if i >= n: break
            tmp = ""
            while (i < n and hits[i] != 0):
                tmp += S[i]
                i += 1
            if (len(tmp) != 0): ans += "<b>" + tmp + "</b>"
        return ans
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018年01月07日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • LWC 66: 758. Bold Words in String
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档