最长有效括号

爱疯

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。


输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"


'-------------------------------------------------------





Sub Solution()
    Dim s As String
    s = ")()(()))"
    MsgBox longestValidParentheses(s)
End Sub


Function longestValidParentheses(s As String) As Integer
    Dim ans, n, i, l, r
    ans = 0: n = Len(s)
    If n = 0 Then longestValidParentheses = 0: Exit Function

    l = 0: r = 0
    For i = 1 To n
        If Mid(s, i, 1) = "(" Then
            l = l + 1
        Else
            r = r + 1
        End If
        If l = r Then
            ans = Application.Max(ans, 2 * r)
        Else
            If r > l Then
                l = 0: r = 0
            End If
        End If
    Next

    l = 0: r = 0
    For i = n To 1 Step -1
        If Mid(s, i, 1) = "(" Then
            l = l + 1
        Else
            r = r + 1
        End If
        If l = r Then
            ans = Application.Max(ans, 2 * r)
        Else
            If l > r Then
                l = 0: r = 0
            End If
        End If
    Next

    longestValidParentheses = ans
End Function


请问：怎么证明该方法是正确的？
谢谢！

wanghan519

最近正好在学正则平衡组，只有php、perl、c#支持这样的写法，可以递归的匹配配对的左右括号，不知道有没有帮助

半百

这个对不对？

1. Sub test()
   
2. s = ")(()(()))("
   
3. 1:
   
4. For i = 1 To Len(s)
   
5.     If Mid(s, i, 1) = "(" Then
   
6.         n = i
   
7.     ElseIf Mid(s, i, 1) = ")" Then
   
8.         If n > 0 Then
   
9.             m = m + 2
   
10.             Mid(s, n) = "|"
    
11.             Mid(s, i) = "|"
    
12.             n = 0
    
13.             GoTo 1
    
14.         End If
    
15.     End If
    
16. Next
    
17. MsgBox m
    
18. End Sub
    

复制代码

cidanji

没看懂，是这个意思吗

1. UBound(Split(s, "()")) * 2

复制代码

爱疯

wanghan519 发表于 2024-1-6 04:48
最近正好在学正则平衡组，只有php、perl、c#支持这样的写法，可以递归的匹配配对的左右括号，不知道有没有 ...

谢谢 wanghan519 !
如果要有学正则的，应该会有帮助的。我不大会正则

爱疯

半百 发表于 2024-1-6 11:41
这个对不对？

谢谢 半百 ！
3楼是暴力的思路：每次从头到尾，先找左再找右，并把找到的两个位置上的字符，替换为指定字符。


因为只是括号对的计数，没判断 格式正确且连续，
所以会有这种错误，s = ")(())(()" ，返回是4，不是6。

爱疯

cidanji 发表于 2024-1-6 13:01
没看懂，是这个意思吗

谢谢 cidanji ！
题意大致如1楼所说

jiangxiaoyun

这个题目好像超人版主就玩过了，上个月拿出来用365函数搞，那些大佬可厉害了。

爱疯

jiangxiaoyun 发表于 2024-1-7 12:12
这个题目好像超人版主就玩过了，上个月拿出来用365函数搞，那些大佬可厉害了。

发这贴的目的是，是想解释1楼方法为什么会是对的，
比如，为什么非要正反各遍历一次？


如果s本身是有效的，无论正反，遍历一次即可。比如 s = "(()())"
...........无....，必须正反各遍历一次才行。比如 s =  ，，，，，，，，，还在想例子


就像看魔术，明知道有一个原因，就是一下子说不上来

wanghan519

爱疯 发表于 2024-1-8 09:43
发这贴的目的是，是想解释1楼方法为什么会是对的，
比如，为什么非要正反各遍历一次？

从前向后好像找不到这个
()((()())
从后向前找不到这个
(()()))()