Cho văn bản text và danh sách patterns. Bọc tất cả chuỗi con khớp pattern nào đó bằng thẻ <b> và </b>. Nếu các pattern kề nhau hoặc chồng chéo, gộp thành một thẻ.
Ví dụ: text = "thisissampleline", patterns = ["this", "ssam", "sample"] → "<b>this</b>i<b>ssample</b>line".
Giải pháp: Mảng bold đánh dấu vị trí cần bold. Duyệt từng vị trí, kiểm tra tiền tố khớp pattern, đánh dấu True. Sau đó xây chuỗi kết quả: mở thẻ khi bold[i] và (i==0 or not bold[i-1]), đóng khi bold[i] và (i==n-1 or not bold[i+1]).
Ví dụ triển khai
class Solution:
def solve(self, text, patterns):
n = len(text)
bold = [False] * n
for i in range(n):
for p in patterns:
if text[i:].startswith(p):
for j in range(len(p)):
bold[i + j] = True
ans = ""
for i in range(n):
if bold[i] and (i == 0 or not bold[i - 1]):
ans += ""
ans += text[i]
if bold[i] and (i == n - 1 or not bold[i + 1]):
ans += ""
return ans
ob = Solution()
text = "thisissampleline"
patterns = ["this", "ssam", "sample"]
print(ob.solve(text, patterns))
Đầu vào
"thisissampleline", ["this", "ssam", "sample"]
Đầu ra
thisissampleline