0758. 字符串中的加粗单词

# 0758. 字符串中的加粗单词#

• 标签：字典树、数组、哈希表、字符串、字符串匹配
• 难度：中等

## 代码 #

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61  class Trie: def __init__(self): """ Initialize your data structure here. """ self.children = dict() self.isEnd = False def insert(self, word: str) -> None: """ Inserts a word into the trie. """ cur = self for ch in word: if ch not in cur.children: cur.children[ch] = Trie() cur = cur.children[ch] cur.isEnd = True def search(self, word: str) -> bool: """ Returns if the word is in the trie. """ cur = self for ch in word: if ch not in cur.children: return False cur = cur.children[ch] return cur is not None and cur.isEnd class Solution: def boldWords(self, words: List[str], s: str) -> str: trie_tree = Trie() for word in words: trie_tree.insert(word) size = len(s) bold_left, bold_right = -1, -1 ans = "" for i in range(size): cur = trie_tree if s[i] in cur.children: bold_left = i while bold_left < size and s[bold_left] in cur.children: cur = cur.children[s[bold_left]] bold_left += 1 if cur.isEnd: if bold_right == -1: ans += "" bold_right = max(bold_left, bold_right) if i == bold_right: ans += "" bold_right = -1 ans += s[i] if bold_right >= 0: ans += "" return ans