Задача: 616. Add Bold Tag in String
Сложность: medium

Вам дана строка s и массив строк words. Вы должны добавить закрытую пару полужирных тегов <b> и </b>, чтобы обернуть подстроки в s, которые существуют в words. Если две такие подстроки пересекаются, вы должны обернуть их вместе только одной парой закрытых полужирных тегов. Если две подстроки, обернутые полужирными тегами, идут подряд, вы должны объединить их. Верните s после добавления полужирных тегов.

Пример:

Input: s = "abcxyz123", words = ["abc","123"]
Output: "<b>abc</b>xyz<b>123</b>"

👨‍💻 Алгоритм:

1⃣Найдите все позиции вхождений подстрок из words в строку s и пометьте эти позиции для выделения тегами <b> и </b>.

2⃣Пройдитесь по помеченным позициям, чтобы определить области, которые нужно обернуть в полужирные теги, слияя пересекающиеся и смежные области.

3⃣Постройте новую строку s, добавляя теги <b> и </b> в определенные позиции.

😎 Решение:

func addBoldTag(_ s: String, _ words: [String]) -> String {
    var bold = Array(repeating: false, count: s.count)
    let sArray = Array(s)
    
    for word in words {
        var start = s.startIndex
        while let range = s.range(of: word, range: start..<s.endIndex) {
            let startIdx = s.distance(from: s.startIndex, to: range.lowerBound)
            let endIdx = s.distance(from: s.startIndex, to: range.upperBound)
            for i in startIdx..<endIdx {
                bold[i] = true
            }
            start = range.lowerBound < s.index(before: s.endIndex) ? s.index(after: range.lowerBound) : s.endIndex
        }
    }
    
    var result = ""
    var i = 0
    while i < sArray.count {
        if bold[i] {
            result += "<b>"
            while i < sArray.count && bold[i] {
                result += String(sArray[i])
                i += 1
            }
            result += "</b>"
        } else {
            result += String(sArray[i])
            i += 1
        }
    }
    
    return result
}

Ставь 👍 и забирай 📚 Базу знаний