LeetCode 32. 最大有効かっこPython/Java

'('および')'のみを含む文字列が与えられ、最も長い有効な括弧を含むサブ列の長さが見出される.
例1:

  : "(()"
  : 2
  :           "()"

例2:

  : ")()())"
  : 4
  :           "()()"

考え方:1.スタックを使用して操作します.左かっこの場合、直接stackに入ります.右かっこの場合、stackに要素ペアがない場合は、有効カッコが終了したことを示します.開始位置を更新します.要素ペアがpopに対して左かっこペアを出します.この場合、有効カッコを継続しない保証はありません.そのため、現在の最長距離に基づいてmaxlenを更新します.この場合、スタックトップのインデックスから減算して長さを計算します.
コード:

        
class Solution:
    def longestValidParentheses(self, s):
        ans = 0
        n = len(s)
        stack = []
        st = 0
        for i in range(n):
            
            if s[i] == '(':
                stack.append(i)
            else:
                if len(stack) == 0:
                    st = i+ 1
                    continue
                else:
                    stack.pop()
                    if len(stack) == 0:
                        ans = max(ans,i - st + 1)
                    else:
                        ans = max(ans,i-stack[-1])
        return ans

Java版

class Solution {
    public int longestValidParentheses(String s) {
        int ans = 0;
        int n = s.length();
        Stack st = new Stack();
        int index = 0;
        for (int i = 0; i 

構想2:ダイナミックプランニング,dp[i]は開始からi点までの最長有効括弧の長さを表す(i点の場合は有効,この場合iが「(」,無効は0)
コード:

class Solution:
    def longestValidParentheses(self, s):
        s = ')' + s
        n = len(s)
        if n<2:
            return 0
        ans = 0
        
        dp = [0] * n
        
        for i in range(1,n):
            if s[i] == ')':
                if s[i-1-dp[i-1]] == '(':
                    dp[i] = dp[i - 1] + 2
                dp[i] += dp[i-dp[i]]
            ans = max(ans,dp[i])
        return ans