856. Score of Parentheses

leetcode medium

#csharp#leetcode#medium#string

Task

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

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

"()" имеет счёт 1.

AB имеет счёт A + B, где A и B — сбалансированные строки скобок.

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

Пример:

Input: s = "()"

Output: 1

C# solution

matched/original

public class Solution {
    public int ScoreOfParentheses(string S) {
        return F(S, 0, S.Length);
    }
    private int F(string S, int i, int j) {
        int ans = 0, bal = 0;
        for (int k = i; k < j; ++k) {
            bal += S[k] == '(' ? 1 : -1;
            if (bal == 0) {
                if (k - i == 1) ans++;
                else ans += 2 * F(S, i + 1, k);
                i = k + 1;
            }
        }
        return ans;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int ScoreOfParentheses(string S) {
        return F(S, 0, S.size());
    }
    private int F(string S, int i, int j) {
        int ans = 0, bal = 0;
        for (int k = i; k < j; ++k) {
            bal += S[k] == '(' ? 1 : -1;
            if (bal == 0) {
                if (k - i == 1) ans++;
                else ans += 2 * F(S, i + 1, k);
                i = k + 1;
            }
        }
        return ans;
    }
}

Java solution

auto-draft, review before submit

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public int ScoreOfParentheses(String S) {
        return F(S, 0, S.length);
    }
    private int F(String S, int i, int j) {
        int ans = 0, bal = 0;
        for (int k = i; k < j; ++k) {
            bal += S[k] == '(' ? 1 : -1;
            if (bal == 0) {
                if (k - i == 1) ans++;
                else ans += 2 * F(S, i + 1, k);
                i = k + 1;
            }
        }
        return ans;
    }
}

JavaScript solution

matched/original

var scoreOfParentheses = function(S) {
    return F(S, 0, S.length)
}

var F = function(S, i, j) {
    let ans = 0, bal = 0

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

    return ans
}

Go solution

matched/original

func scoreOfParentheses(S string) int {
    return F(S, 0, len(S))
}

func F(S string, i, j int) int {
    ans, bal := 0, 0

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

    return ans
}

Explanation

Algorithm

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

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

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

😎