LeetCode 616: Add Bold Tag in String Solution in Python – A Step-by-Step Guide

What Is LeetCode 616: Add Bold Tag in String?

In LeetCode 616: Add Bold Tag in String, you’re given a string s and a list of words words, and your task is to wrap every occurrence of each word in s with and tags. If bolded sections overlap or are adjacent (e.g., "ab" and "bc" in "abc"), merge them into one continuous bold section (e.g., abc). For example, with s = "abcxyz123" and words = ["abc", "123"], the output is abcxyz123. This problem tests your ability to handle string matching and overlapping intervals efficiently.

Problem Statement

• Input:
• s: A string.
• words: A list of strings to bold.
• Output: A string with and tags around all word occurrences, merged where overlapping or adjacent.
• Rules:
• Bold every occurrence of each word in words.
• Merge bold sections if they overlap or are consecutive.
• Case-sensitive matching.

Constraints

• 1 ≤ s.length ≤ 1000.
• 0 ≤ words.length ≤ 100.
• 1 ≤ words[i].length ≤ 10.
• All strings contain lowercase letters, digits, or special chars.

Examples

• Input: s = "abcxyz123", words = ["abc", "123"]
• Output: "abcxyz123"
• Input: s = "aaabbcc", words = ["aaa", "aab", "bc"]
• Output: "aaabbcc" (aaa and aab merge into aaabb)
• Input: s = "xyz", words = ["z"]
• Output: "xyz"

These examples show the merging—let’s solve it!

Understanding the Problem: Bold Tagging with Merging

To solve LeetCode 616: Add Bold Tag in String in Python, we need to find all occurrences of words in the string, mark their start and end positions, merge overlapping or adjacent intervals, and insert bold tags around those sections. A naive approach might tag each character repeatedly, but we can optimize with intervals. We’ll use:

• Best Solution (Interval Merging): O(n m k) time, O(n) space—efficient and clean (n = string length, m = words length, k = average word length).
• Alternative Solution (Brute-Force Tagging): O(n m k) time, O(n) space—simple but redundant.

Let’s start with the interval merging solution, breaking it down for beginners.

Best Solution: Interval Merging with String Matching

Why This Is the Best Solution

The interval merging approach is the top choice for LeetCode 616 because it’s efficient—O(n * m * k) time—and elegantly handles overlapping bold sections by finding all word occurrences, converting them to intervals, merging them, and then applying tags in one pass. It avoids redundant tagging and scales well within constraints. It’s like marking bold zones on a map and merging them before labeling!

How It Works

Think of this as highlighting text with a marker:

• Step 1: Find Word Occurrences:
• For each word, find all starting indices in s.
• Step 2: Create Intervals:
• Convert each occurrence to [start, end] (end is start + word length).
• Step 3: Merge Intervals:
• Sort intervals by start, merge if overlapping or adjacent (end ≥ next start).
• Step 4: Build Result:
• Iterate through s, insert at interval starts and at ends.
• Step 5: Return String:
• Join the result into a single string.

It’s like a smart text highlighter—merge and tag!

Step-by-Step Example

Example: s = "aaabbcc", words = ["aaa", "aab", "bc"]

• Step 1: Find occurrences:
• "aaa": [0].
• "aab": [1].
• "bc": [4].
• Step 2: Intervals:
• "aaa": [0, 3) (end exclusive).
• "aab": [1, 4).
• "bc": [4, 6).
• Step 3: Merge:
• Sort: [0, 3), [1, 4), [4, 6).
• Merge [0, 3) and [1, 4) (3 ≥ 1) → [0, 4).
• Merge [0, 4) and [4, 6) (4 = 4) → [0, 6).
• Final: [0, 6).
• Step 4: Build:
• At 0: , string = .
• Chars 0-5: "aaabbc" → aaabbc.
• At 6: , aaabbc.
• Char 6: "c" → aaabbcc.
• Output: "aaabbcc".

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def addBoldTag(self, s: str, words: List[str]) -> str:
        # Step 1: Find all intervals
        intervals = []
        for word in words:
            w_len = len(word)
            for i in range(len(s) - w_len + 1):
                if s[i:i + w_len] == word:
                    intervals.append([i, i + w_len])

        # Step 2: Merge intervals
        if not intervals:
            return s
        intervals.sort()  # Sort by start
        merged = []
        for start, end in intervals:
            if not merged or merged[-1][1] < start:
                merged.append([start, end])
            else:
                merged[-1][1] = max(merged[-1][1], end)

        # Step 3: Build result string
        result = []
        i = 0
        for start, end in merged:
            # Add non-bold part before interval
            if i < start:
                result.append(s[i:start])
            # Add bold part
            result.append("<b>" + s[start:end] + "</b>")
            i = end
        # Add remaining non-bold part
        if i < len(s):
            result.append(s[i:])

        # Step 4: Return joined string
        return "".join(result)

• Lines 5-9: Find intervals:
• Check each substring for word matches.
• Lines 12-19: Merge:
• Sort by start, merge if overlapping or adjacent.
• Lines 22-31: Build:
• Add plain text, then bolded sections.
• Time Complexity: O(n m k)—n positions, m words, k avg word length.
• Space Complexity: O(n)—intervals and result.

This is like a text highlighter—efficient and merged!

Alternative Solution: Brute-Force Character Tagging

Why an Alternative Approach?

The brute-force tagging approach marks each character’s bold status—O(n * m * k) time, O(n) space. It’s simpler, tagging each position directly, but it’s less efficient due to redundant checks and no explicit merging logic. It’s like bolding each letter one-by-one!

How It Works

Picture this as marking text with a pen:

• Step 1: Create bold array for each character.
• Step 2: Tag characters in word occurrences.
• Step 3: Build string with tags at transitions.
• Step 4: Return result.

It’s like a character-by-character bold check!

Step-by-Step Example

Example: s = "aaabbcc", words = ["aaa", "aab", "bc"]

• Step 1: bold = [False] * 7.
• Step 2: Tag:
• "aaa" at 0: bold[0:3] = [True, True, True].
• "aab" at 1: bold[1:4] = [True, True, True].
• "bc" at 4: bold[4:6] = [True, True].
• bold = [True, True, True, True, True, True, False].
• Step 3: Build:
• Start: , "aaabbcc" → aaabbcc.
• At 6: , aaabbcc.
• Add "c" → aaabbccc.
• Output: "aaabbccc".

Code for Brute-Force Approach

Copy codeclass Solution:
    def addBoldTag(self, s: str, words: List[str]) -> str:
        # Step 1: Initialize bold array
        n = len(s)
        bold = [False] * n

        # Step 2: Mark bold positions
        for word in words:
            w_len = len(word)
            for i in range(n - w_len + 1):
                if s[i:i + w_len] == word:
                    for j in range(i, i + w_len):
                        bold[j] = True

        # Step 3: Build result
        result = []
        i = 0
        while i < n:
            if bold[i]:
                result.append("<b>")
                while i < n and bold[i]:
                    result.append(s[i])
                    i += 1
                result.append("</b>")
            else:
                result.append(s[i])
                i += 1

        # Step 4: Return joined string
        return "".join(result)

• Lines 5-6: bold array for each char.
• Lines 9-13: Mark bold positions.
• Lines 16-24: Build string with tags.
• Time Complexity: O(n m k)—same as best but with more operations.
• Space Complexity: O(n)—bold array.

It’s a bold marker—simple but repetitive!

Comparing the Two Solutions

• Interval Merging (Best):
• Pros: O(n m k) time, O(n) space, efficient merging.
• Cons: Interval logic less intuitive.
• Brute-Force (Alternative):
• Pros: O(n m k) time, O(n) space, straightforward.
• Cons: Redundant tagging.

Interval merging wins for elegance.

Additional Examples and Edge Cases

• Input: s = "abc", words = []
• Output: "abc".
• Input: s = "a", words = ["a"]
• Output: "a".

Both handle these well.

Complexity Breakdown

• Interval Merging: Time O(n m k), Space O(n).
• Brute-Force: Time O(n m k), Space O(n).

Interval merging is more optimized.

Key Takeaways

• Interval Merging: Smart merging—efficient!
• Brute-Force: Character tagging—clear!
• Strings: Manipulation is fun.
• Python Tip: Lists rock—see Python Basics.

Final Thoughts: Bold That Text

LeetCode 616: Add Bold Tag in String in Python is a neat string-manipulation challenge. Interval merging offers efficiency and elegance, while brute-force keeps it simple. Want more? Try LeetCode 68: Text Justification or LeetCode 758: Bold Words in String. Ready to highlight? Head to Solve LeetCode 616 on LeetCode and bold those words today!