Question

758. 字符串中的加粗单词

English Version

题目描述

给定一个关键词集合 words 和一个字符串 s，将所有 s 中出现的关键词 words[i] 加粗。所有在标签 <b> 和 <b> 中的字母都会加粗。

加粗后返回 s 。返回的字符串需要使用尽可能少的标签，当然标签应形成有效的组合。

 

示例 1:

输入: words = ["ab","bc"], s = "aabcd"
输出: "a<b>abc</b>d"
解释: 注意返回 "a<b>a<b>b</b>c</b>d" 会使用更多的标签，因此是错误的。

示例 2:

输入: words = ["ab","cb"], s = "aabcd"
输出: "a<b>ab</b>cd"

 

提示:

• 1 <= s.length <= 500
• 0 <= words.length <= 50
• 1 <= words[i].length <= 10
• s 和 words[i] 由小写英文字母组成

 

注：此题与「616 - 给字符串添加加粗标签」相同 - https://leetcode.cn/problems/add-bold-tag-in-string/

解法

方法一：前缀树 + 区间合并

相似题目：

• 1065. 字符串的索引对
• 616. 给字符串添加加粗标签

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 boldWords(self, words: List[str], s: 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)

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 boldWords(String[] words, String s) {
    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 boldWords(vector<string>& words, string s) {
    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;
  }
};

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 boldWords(words []string, s 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()
}