LeetCode 616: Add Bold Tag in String Solution

Master LeetCode problem 616 (Add Bold Tag in String), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

616. Add Bold Tag in String

Medium

Array Hash Table String Trie String Matching

Problem Explanation

Explanation:

To solve this problem, we can iterate through the given string and maintain a boolean array isBold to keep track of which characters should be bolded. We can update this array based on the given list of substrings to be bolded. Once we have updated the isBold array, we can construct the final bolded string.

Algorithm:

Initialize a boolean array isBold of size equal to the length of the input string, initially set all elements to false.
Iterate over each substring to be bolded.
For each substring, find all occurrences in the input string and mark the corresponding elements in the isBold array as true.
Construct the final bolded string by iterating over the input string and adding <b> and </b> tags where necessary based on the isBold array.

Time Complexity:

The time complexity of this approach is O(n*m) where n is the length of the input string and m is the total number of characters in the substrings to be bolded.

Space Complexity:

The space complexity of this approach is O(n) where n is the length of the input string.

: :

Solution Code

class Solution {
    public String addBoldTag(String s, String[] dict) {
        boolean[] isBold = new boolean[s.length()];
        
        for (String word : dict) {
            int index = s.indexOf(word);
            while (index != -1) {
                for (int i = index; i < index + word.length(); i++) {
                    isBold[i] = true;
                }
                index = s.indexOf(word, index + 1);
            }
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (isBold[i] && (i == 0 || !isBold[i - 1])) {
                sb.append("<b>");
            }
            sb.append(s.charAt(i));
            if (isBold[i] && (i == s.length() - 1 || !isBold[i + 1])) {
                sb.append("</b>");
            }
        }
        
        return sb.toString();
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 616 (Add Bold Tag in String)?

This page provides optimized solutions for LeetCode problem 616 (Add Bold Tag in String) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

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

The time complexity for LeetCode 616 (Add Bold Tag in String) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 616 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 616 in Java, C++, or Python.

Back to LeetCode Solutions