返回介绍

solution / 0700-0799 / 0758.Bold Words in String / README_EN

发布于 2024-06-17 01:03:34 字数 8274 浏览 0 评论 0 收藏 0

758. Bold Words in String

中文文档

Description

Given an array of keywords words and a string s, make all appearances of all keywords words[i] in s bold. Any letters between <b> and </b> tags become bold.

Return s _after adding the bold tags_. The returned string should use the least number of tags possible, and the tags should form a valid combination.

 

Example 1:

Input: words = ["ab","bc"], s = "aabcd"
Output: "a<b>abc</b>d"
Explanation: Note that returning "a<b>a<b>b</b>c</b>d" would use more tags, so it is incorrect.

Example 2:

Input: words = ["ab","cb"], s = "aabcd"
Output: "a<b>ab</b>cd"

 

Constraints:

  • 1 <= s.length <= 500
  • 0 <= words.length <= 50
  • 1 <= words[i].length <= 10
  • s and words[i] consist of lowercase English letters.

 

Note: This question is the same as 616: https://leetcode.com/problems/add-bold-tag-in-string/

Solutions

Solution 1

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()
}

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
    原文