题目描述
难度分:$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$。观察之后可以发现如下规律:
- 如果$left \gt 0$和$right \gt 0$同时成立,这个字符串就应该被抛弃掉,不可能存在能和它匹配出合法括号串的另一个字符串。
- 如果$left \gt 0$,就把它记录到哈希表$lcnt$中($lcnt$的映射关系为“左括号净含量 $\rightarrow$ 这个净含量的字符串数目”)。
- 如果$right \gt 0$,就把它记录到哈希表$rcnt$中($rcnt$的映射关系为“右括号净含量 $\rightarrow$ 这个净含量的字符串数目”)。
- 如果$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;
}