Задача: 856. Score of Parentheses
Сложность: medium

Дана строка s, состоящая из сбалансированных скобок, верните счёт строки.

Счёт сбалансированной строки скобок основывается на следующих правилах:

"()" имеет счёт 1.
AB имеет счёт A + B, где A и B — сбалансированные строки скобок.
(A) имеет счёт 2 * A, где A — сбалансированная строка скобок.

Пример:

Input: s = "()"
Output: 1

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

1⃣Назовём сбалансированную строку примитивной, если её нельзя разделить на две непустые сбалансированные строки.

2⃣Отслеживая баланс (количество открывающих скобок минус количество закрывающих скобок), мы можем разделить строку S на примитивные подстроки S = P_1 + P_2 + ... + P_n. Тогда, по определению, score(S) = score(P_1) + score(P_2) + ... + score(P_n).

3⃣Для каждой примитивной подстроки (S[i], S[i+1], ..., S[k]), если длина строки равна 2, то её счёт равен 1. В противном случае, счёт равен удвоенному счёту подстроки (S[i+1], S[i+2], ..., S[k-1]).

😎 Решение:

class Solution {
    function scoreOfParentheses($S) {
        return $this->F($S, 0, strlen($S));
    }

    function F($S, $i, $j) {
        $ans = 0;
        $bal = 0;

        for ($k = $i; $k < $j; $k++) {
            $bal += $S[$k] === '(' ? 1 : -1;
            if ($bal === 0) {
                if ($k - $i === 1) {
                    $ans++;
                } else {
                    $ans += 2 * $this->F($S, $i + 1, $k);
                }
                $i = $k + 1;
            }
        }

        return $ans;
    }
}

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