How hard is LeetCode 616. Add Bold Tag in String?

LeetCode 616. Add Bold Tag in String is rated Medium on LeetCode.

What is the time complexity of LeetCode 616. Add Bold Tag in String?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 616. Add Bold Tag in String?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 616. Add Bold Tag in String cover?

LeetCode 616. Add Bold Tag in String is tagged Trie, Array, Hash Table, String and String Matching on LeetCode.

Is LeetCode 616. Add Bold Tag in String a premium problem?

Yes. LeetCode 616. Add Bold Tag in String is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Add Bold Tag in String — LeetCode 616 Python Solution

MediumLeetCode PremiumTrieArrayHash TableStringString Matching

Problem: #616
Pattern: Trie
Reading time: 10 min
Source: leetcode.com

The problem

You are given a string s and an array of strings words. You should add a closed pair of bold tag and to wrap the substrings in s that exist in words.

Example

Input: s = "abcxyz123", words = ["abc","123"]
Output: "abcxyz123"
Explanation: The two strings of words are substrings of s as following: "abcxyz123".

Python solution

Python

class Trie:
    def __init__(self):
        self.children = [None] * 128
        self.is_end = False

    def insert(self, word):
        node = self
        for c in word:
            idx = ord(c)
            if node.children[idx] is None:
                node.children[idx] = Trie()
            node = node.children[idx]
        node.is_end = True


class Solution:
    def addBoldTag(self, s: str, words: List[str]) -> str:
        trie = Trie()
        for w in words:
            trie.insert(w)
        n = len(s)
        pairs = []
        for i in range(n):
            node = trie
            for j in range(i, n):
                idx = ord(s[j])
                if node.children[idx] is None:
                    break
                node = node.children[idx]
                if node.is_end:
                    pairs.append([i, j])
        if not pairs:
            return s
        st, ed = pairs[0]
        t = []
        for a, b in pairs[1:]:
            if ed + 1 < a:
                t.append([st, ed])
                st, ed = a, b
            else:
                ed = max(ed, b)
        t.append([st, ed])

        ans = []
        i = j = 0
        while i < n:
            if j == len(t):
                ans.append(s[i:])
                break
            st, ed = t[j]
            if i < st:
                ans.append(s[i:st])
            ans.append('<b>')
            ans.append(s[st : ed + 1])
            ans.append('</b>')
            j += 1
            i = ed + 1

        return ''.join(ans)

Complexity

Measure	Complexity
Time	O(n)
Space	O(n) auxiliary

Pattern: Trie

Store a set of words by their shared prefixes so lookups cost the length of the word. LeetCode 616. Add Bold Tag in String is filed here because LeetCode tags it Trie, which is the vocabulary this hub collects.

The trie guide has the Python template for the pattern and the 49 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 616. Add Bold Tag in String?: LeetCode 616. Add Bold Tag in String is rated Medium on LeetCode.
What is the time complexity of LeetCode 616. Add Bold Tag in String?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 616. Add Bold Tag in String?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 616. Add Bold Tag in String cover?: LeetCode 616. Add Bold Tag in String is tagged Trie, Array, Hash Table, String and String Matching on LeetCode.
Is LeetCode 616. Add Bold Tag in String a premium problem?: Yes. LeetCode 616. Add Bold Tag in String is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.