最长括号匹配的题解(4种)(第30场周赛整理)
y总的题解:开心消消乐法
算法核心:(1) 最长合法括号序列肯定不会重合
(2) 依据前缀和必须处处大于0
(3) 已匹配的括号可以消去
for (int i = 0; s[i]; i ++ )
{
if (stk.size() && s[i] == ')' && s[stk.top()] == '(') stk.pop();
else stk.push(i);
int r;
if (stk.size()) r = i - stk.top();
else r = i + 1;
if (r > resl) resl = r, resc = 1;
else if (r > 0 && r == resl) resc ++ ;
}
灵茶山艾府的题解:利用前缀和切割片段
算法核心:(1)从左往右扫描一遍,从右往左扫描一遍,
可以将所有最长合法括号序列全部匹配到
x := 0
for i, c := range s {
if c == '(' {
x++
} else if x > 0 {
x--
} else {
t[i] = ' ' // 从左往右扫描,将无法与左括号匹配的右括号标记为空格
}
}
x = 0
for i := len(s) - 1; i >= 0; i-- {
if s[i] == ')' {
x++
} else if x > 0 {
x--
} else {
t[i] = ' ' // 从右往左扫描,将无法与右括号匹配的左括号标记为空格
}
}
jimmy2021的题解:dp的思路
(1)核心算法思想:d[i]为以i为结尾的最长括号序列
如果d[i-1]为0,代表中间出现间隔,如果间隔位为),显然舍去
如果为(,则进一步考虑i-2位,d[i]=2+d[i-2];
如果d[i-1]不为0,那么可以从i-1位转移,因为i-1位已经匹配到了i-d[i-1]-1位,
所以从那边接着像后面接
for(int i=1;i<=n;i++)
{
if(s[i]=='(') continue;
else
{
if(d[i-1]==0)
{
if(s[i-1]=='(') d[i]=2+d[i-2];
else d[i]=0;
}
else
{
if(s[i-d[i-1]-1]=='(') d[i]=d[i-1]+2+d[i-d[i-1]-2];
else d[i]=0;
}
}
}
今夕的题解:也是在dp,不过思路和上一个有点差别
f[i]表示到第i位为止,已经匹配了多长的字符串
算法核心:(1) 匹配的括号序列可以由左括号确定
(2) 右括号,如果可以匹配的话,我们top--,非法右括号的出现,
是因为左括号已经匹配完了,此时可以忽略
(3) 所以就有 f[i] = f[st[top] - 1] + (i - st[top] + 1);的出现
rep(i,1,n) {
if(s[i] == '(') {
st[++top] = i;
} else {
if(top) {
f[i] = f[st[top] - 1] + (i - st[top] + 1);
top --;
}
}
}