题目描述

难度分:$1500$

输入$n(1 \leq n \leq 3 \times 10^5)$长为$n$的括号字符串数组$s$，字符串长度之和$\leq 3 \times 10^5$。

输出有多少个$(i,j)$使得$s[i]+s[j]$是合法括号字符串。

注意$i$可以等于$j$，也可以大于$j$。

输入样例$1$

7
)())
)
((
((
(
)
)

输出样例$1$

2

输入样例$2$

4
(
((
(((
(())

输出样例$2$

4

算法

这个题目和昨天的几乎一样，可以用同一个贪心策略。

贪心

每个字符串从左往右遍历，按照括号匹配的思路计算最后剩下的左括号“净含量”$left$和右括号“净含量”$right$。观察之后可以发现如下规律：

1. 如果$left \gt 0$和$right \gt 0$同时成立，这个字符串就应该被抛弃掉，不可能存在能和它匹配出合法括号串的另一个字符串。
2. 如果$left \gt 0$，就把它记录到哈希表$lcnt$中（$lcnt$的映射关系为“左括号净含量 $\rightarrow$ 这个净含量的字符串数目”）。
3. 如果$right \gt 0$，就把它记录到哈希表$rcnt$中（$rcnt$的映射关系为“右括号净含量 $\rightarrow$ 这个净含量的字符串数目”）。
4. 如果$left=right=0$，记录满足这个的字符串数目$zcnt$，这样的字符串可以两两配对，一共产生$zcnt^2$个合法括号串。

接下来就是让左括号“净含量”与右括号“净含量”相等的串进行配对，对于一个在$lcnt$和$rcnt$都存在的“净含量”$x$，它对答案的贡献为$lcnt[x] \times rcnt[x]$，把这些$x$的贡献都累加起来就是答案。

复杂度分析

时间复杂度

遍历了$n$个字符串一次，对于每个字符串，需要遍历它的每个字符，而字符串长度的总和也是$O(n)$的，因此遍历的时间复杂度为$O(n)$。

之后要遍历哈希表$lcnt$，对每个$key$都要检查其是否也在$rcnt$中，从而计算最大配对数。在最差情况下每个字符串的左括号净含量都不同，有$O(n)$级别的$key$数量，因此遍历的时间复杂度为$O(n)$。

综上，整个算法的时间复杂度为$O(n)$。

空间复杂度

开辟了$lcnt$和$rcnt$两个哈希表的空间，在最差情况下这两个哈希表会存$O(n)$级别的键值对，因此算法整体的额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;
typedef long long LL;

int n;

int main() {
    scanf("%d", &n);
    string s;
    int zcnt = 0;
    unordered_map<int, int> lcnt, rcnt;
    for(int i = 0; i < n; i++) {
        cin >> s;
        int left = 0, right = 0;
        for(char c: s) {
            if(c == '(') {
                left++;
            }else {
                if(left) left--;
                else right++;
            }
        }
        if(left && right) continue;
        if(left) lcnt[left]++;
        if(right) rcnt[right]++;
        if(left == 0 && right == 0) zcnt++;
    }
    LL ans = (LL)zcnt*zcnt;
    for(auto&[k, v]: lcnt) {
        if(rcnt.find(k) != rcnt.end()) {
            ans += (LL)v*rcnt[k];
        }
    }
    printf("%lld\n", ans);
    return 0;
}