Welcome to Subscribe On Youtube

616. Add Bold Tag in String

Description

You are given a string s and an array of strings words.

You should add a closed pair of bold tag <b> and </b> to wrap the substrings in s that exist in words.

  • If two such substrings overlap, you should wrap them together with only one pair of closed bold-tag.
  • If two substrings wrapped by bold tags are consecutive, you should combine them.

Return s after adding the bold tags.

 

Example 1:

Input: s = "abcxyz123", words = ["abc","123"]
Output: "<b>abc</b>xyz<b>123</b>"
Explanation: The two strings of words are substrings of s as following: "abcxyz123".
We add <b> before each substring and </b> after each substring.

Example 2:

Input: s = "aaabbb", words = ["aa","b"]
Output: "<b>aaabbb</b>"
Explanation: 
"aa" appears as a substring two times: "aaabbb" and "aaabbb".
"b" appears as a substring three times: "aaabbb", "aaabbb", and "aaabbb".
We add <b> before each substring and </b> after each substring: "<b>a<b>a</b>a</b><b>b</b><b>b</b><b>b</b>".
Since the first two <b>'s overlap, we merge them: "<b>aaa</b><b>b</b><b>b</b><b>b</b>".
Since now the four <b>'s are consecutive, we merge them: "<b>aaabbb</b>".

 

Constraints:

  • 1 <= s.length <= 1000
  • 0 <= words.length <= 100
  • 1 <= words[i].length <= 1000
  • s and words[i] consist of English letters and digits.
  • All the values of words are unique.

 

Note: This question is the same as 758: https://leetcode.com/problems/bold-words-in-string/

Solutions

  • class Trie {
        Trie[] children = new Trie[128];
        boolean isEnd;
    
        public void insert(String word) {
            Trie node = this;
            for (char c : word.toCharArray()) {
                if (node.children[c] == null) {
                    node.children[c] = new Trie();
                }
                node = node.children[c];
            }
            node.isEnd = true;
        }
    }
    
    class Solution {
        public String addBoldTag(String s, String[] words) {
            Trie trie = new Trie();
            for (String w : words) {
                trie.insert(w);
            }
            List<int[]> pairs = new ArrayList<>();
            int n = s.length();
            for (int i = 0; i < n; ++i) {
                Trie node = trie;
                for (int j = i; j < n; ++j) {
                    int idx = s.charAt(j);
                    if (node.children[idx] == null) {
                        break;
                    }
                    node = node.children[idx];
                    if (node.isEnd) {
                        pairs.add(new int[] {i, j});
                    }
                }
            }
            if (pairs.isEmpty()) {
                return s;
            }
            List<int[]> t = new ArrayList<>();
            int st = pairs.get(0)[0], ed = pairs.get(0)[1];
            for (int j = 1; j < pairs.size(); ++j) {
                int a = pairs.get(j)[0], b = pairs.get(j)[1];
                if (ed + 1 < a) {
                    t.add(new int[] {st, ed});
                    st = a;
                    ed = b;
                } else {
                    ed = Math.max(ed, b);
                }
            }
            t.add(new int[] {st, ed});
            int i = 0, j = 0;
            StringBuilder ans = new StringBuilder();
            while (i < n) {
                if (j == t.size()) {
                    ans.append(s.substring(i));
                    break;
                }
                st = t.get(j)[0];
                ed = t.get(j)[1];
                if (i < st) {
                    ans.append(s.substring(i, st));
                }
                ++j;
                ans.append("<b>");
                ans.append(s.substring(st, ed + 1));
                ans.append("</b>");
                i = ed + 1;
            }
            return ans.toString();
        }
    }
    
  • class Trie {
    public:
        vector<Trie*> children;
        bool isEnd;
    
        Trie() {
            children.resize(128);
            isEnd = false;
        }
    
        void insert(string word) {
            Trie* node = this;
            for (char c : word) {
                if (!node->children[c]) node->children[c] = new Trie();
                node = node->children[c];
            }
            node->isEnd = true;
        }
    };
    
    class Solution {
    public:
        string addBoldTag(string s, vector<string>& words) {
            Trie* trie = new Trie();
            for (string w : words) trie->insert(w);
            int n = s.size();
            vector<pair<int, int>> pairs;
            for (int i = 0; i < n; ++i) {
                Trie* node = trie;
                for (int j = i; j < n; ++j) {
                    int idx = s[j];
                    if (!node->children[idx]) break;
                    node = node->children[idx];
                    if (node->isEnd) pairs.push_back({i, j});
                }
            }
            if (pairs.empty()) return s;
            vector<pair<int, int>> t;
            int st = pairs[0].first, ed = pairs[0].second;
            for (int i = 1; i < pairs.size(); ++i) {
                int a = pairs[i].first, b = pairs[i].second;
                if (ed + 1 < a) {
                    t.push_back({st, ed});
                    st = a, ed = b;
                } else
                    ed = max(ed, b);
            }
            t.push_back({st, ed});
            string ans = "";
            int i = 0, j = 0;
            while (i < n) {
                if (j == t.size()) {
                    ans += s.substr(i);
                    break;
                }
                st = t[j].first, ed = t[j].second;
                if (i < st) ans += s.substr(i, st - i);
                ans += "<b>";
                ans += s.substr(st, ed - st + 1);
                ans += "</b>";
                i = ed + 1;
                ++j;
            }
            return ans;
        }
    };
    
  • 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)
    
    
  • type Trie struct {
    	children [128]*Trie
    	isEnd    bool
    }
    
    func newTrie() *Trie {
    	return &Trie{}
    }
    
    func (this *Trie) insert(word string) {
    	node := this
    	for _, c := range word {
    		if node.children[c] == nil {
    			node.children[c] = newTrie()
    		}
    		node = node.children[c]
    	}
    	node.isEnd = true
    }
    
    func addBoldTag(s string, words []string) string {
    	trie := newTrie()
    	for _, w := range words {
    		trie.insert(w)
    	}
    	n := len(s)
    	var pairs [][]int
    	for i := range s {
    		node := trie
    		for j := i; j < n; j++ {
    			if node.children[s[j]] == nil {
    				break
    			}
    			node = node.children[s[j]]
    			if node.isEnd {
    				pairs = append(pairs, []int{i, j})
    			}
    		}
    	}
    	if len(pairs) == 0 {
    		return s
    	}
    	var t [][]int
    	st, ed := pairs[0][0], pairs[0][1]
    	for i := 1; i < len(pairs); i++ {
    		a, b := pairs[i][0], pairs[i][1]
    		if ed+1 < a {
    			t = append(t, []int{st, ed})
    			st, ed = a, b
    		} else {
    			ed = max(ed, b)
    		}
    	}
    	t = append(t, []int{st, ed})
    	var ans strings.Builder
    	i, j := 0, 0
    	for i < n {
    		if j == len(t) {
    			ans.WriteString(s[i:])
    			break
    		}
    		st, ed = t[j][0], t[j][1]
    		if i < st {
    			ans.WriteString(s[i:st])
    		}
    		ans.WriteString("<b>")
    		ans.WriteString(s[st : ed+1])
    		ans.WriteString("</b>")
    		i = ed + 1
    		j++
    	}
    	return ans.String()
    }
    

All Problems

All Solutions