Leetcode 032最長有効括弧構想詳細解+反省総括python

私はずっとLeetcodeの上でPythonで実現した問題を蓄積して、しかも全力を尽くしてすべての問題の原理をはっきり言って、決して他のいくつかのブログのように簡単に持っていません.
はっきり言っていると思ったら、注目してください.'('のみを含む ')' の文字列で、最も長い有効な括弧を含むサブ列の長さを見つけます.
例 1:

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

例2:

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

構想一:スタック
考え方1:スタックに入ってスタックを出る方法でかっこのindexを保存します.このstack、右かっこは中に入りたいですが、前のstackの上部要素も右かもしれませんが、最初の右かっこはどうやって入りますか?stackが空いているときにしか入れません.そして、入るには連続して入らなければなりません.そうしないと、最新の左括弧popを出してこそ入ることができます.

#        ，                       
class Solution:
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        j = len(s)
        maxlen = 0
        #stack          （      ，       ） s  index
        stack = []
        #  index
        for i in range(j):
            #              stack      pop  
            #      pop         ，   pop
            if s[i] == ')' and len(stack) != 0 and s[stack[-1]] == '(':
                a = stack.pop()
                #  pop    stack   0，                              
                #          maxlen
                if len(stack) == 0:
                    maxlen = i + 1
                #         ，            
                else:
                    maxlen = max(maxlen, i - stack[-1])

            else:
                stack.append(i)

        return maxlen

しかし、この書き方は少しはっきりしていないので、はっきりしたものを見てみましょう.
考え方:左かっこに遭遇したときだけスタックに入れます.この問題はvalid parenthesesの拡張であり,スタック構造を利用して実現することもできる.ここでは、左かっこの下付き文字をスタックで保存し、左カッコに遭遇したら、その下付き文字をスタックに保存します.右かっこに遭遇した場合、スタックが空の場合、これは有効カッコペアではないことを説明し、スキップし、有効カッコの開始点を更新します.スタックが空でない場合、スタックの上部要素はスタックから出ます.この場合、スタックが空の場合、後に合法的な有効カッコペアが接続されていないとは限らないので、現在と有効カッコの開始点の距離を計算し、最大値を更新します.空でない場合は、()()()()()などのmaxlenを現在の位置からスタックトップ要素までの距離とmaxlenの最大値で更新します.Grandyangのブログを参照してください.

class Solution:
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        tl = len(s)
        stack = []
        st = 0
        maxlen = 0
        for i in range(tl):
            #      ，   stack
            if s[i] == '(':
                stack.append(i)
            #     
            else:
                #  stack       ，          ，      
                if len(stack) == 0:
                    st = i+1
                    continue
                #     
                else:
                    a = stack.pop()
                    #pop        
                    #      ，           ，              maxlen
                    if len(stack) == 0:
                        maxlen = max(i - st+1, maxlen)
                    #                       
                    else:
                        maxlen = max(i-stack[-1], maxlen)

        return maxlen

構想二:動的計画
この問題はダイナミックプランニングの方法で解くこともできます.
dp[i]はiまでの最長有効かっこであり、s[i]が左かっこである場合、dp[i]は0である.文字列が左かっこで終わると有効になるはずがないからである.右かっこである場合、2つの場合がある.
一:前者s[i-1]は左かっこであるため、dp[i]=dp[i-2]+2;
二、s[i-1]は右括弧、s[i-dp[i-1]-1]は左括弧であるため、i-dp[i]=dp[i-1]+2+dp[i-dp[i-1]-2は最長括弧の始点に対応する
LeetCode OJコードは以下の通りです.
class
Solution
:
def
longestValidParentheses
(
self
,
s
):
"""
:type s: str
:rtype: int
"""
a
=
len
(s)
if
a
<
2
:
return
0
maxlen
=
0
#dp[i]は、ちょうどs[i]以前(s[i]を含む)の最長括弧の長さを表す
#s[i]='(',dp[i]=0の場合
dp
=
[
0
for
_
in
range
(a)]
for
i
in
range
(
1
, a):
#現在のiの対称点のインデックス
pos
=
i
-
1
-
dp[i
-
1
]
if
s[i]
==
')'
and
s[i
-
1
]
==
'('
and
i
-
2
>=
0
:
#前項の最長長+2に等しい
dp[i]
=
dp[i
-
2
]
+
2
elif
s[i]
==
')'
and
pos
>=
0
and
s[pos]
==
'('
:
#前の対称点+2に等しい
dp[i]
=
dp[i
-
1
]
+
2
if
pos
-
1
>=
0
:
対称点の前に長さがある場合は、その長さを加えます.
dp[i]
+=
dp[i
-
dp[i
-
1
]
-
2
]
return
max
(dp)