#ЛитКод
Задача: 616. Add Bold Tag in String

Вам дана строка 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> в определенные позиции.

😎 Решение:

function addBoldTag($s, $words) {
    $bold = array_fill(0, strlen($s), false);
    
    foreach ($words as $word) {
        $pos = strpos($s, $word);
        while ($pos !== false) {
            for ($i = $pos; $i < $pos + strlen($word); $i++) {
                $bold[$i] = true;
            }
            $pos = strpos($s, $word, $pos + 1);
        }
    }
    
    $result = "";
    $i = 0;
    while ($i < strlen($s)) {
        if ($bold[$i]) {
            $result .= "<b>";
            while ($i < strlen($s) && $bold[$i]) {
                $result .= $s[$i];
                $i++;
            }
            $result .= "</b>";
        } else {
            $result .= $s[$i];
            $i++;
        }
    }
    
    return $result;
}

👉Новости 👉Платформа