Pythonで指定された文字列から最長の有効な括弧の長さを見つけるプログラム

文字列sがあるとします。これは、開き括弧と閉じ括弧のみで構成されます。有効な（整形式の）最も長い括弧の部分文字列の長さを見つける必要があります。したがって、入力が「））（（））（））」の場合、有効な文字列は「（（））（）」であるため、結果は6になります。

これを解決するには、次の手順に従います-

• スタックを作成し、-1を挿入し、ans：=0

  を設定します。

• 0からスタックの長さまでの範囲のiの場合– 1

  • s [i]が開き括弧の場合は、iをスタックに挿入します

  • それ以外の場合

    • スタックが空でなく、スタックの最上位が-1でなく、s [stack top]が開き括弧である場合、

      • スタックの最上位要素

      • ans：=ansとiの最大値–スタックトップ

    • それ以外の場合は、iをスタックに挿入します

• ansを返す

例

理解を深めるために、次の実装を見てみましょう-

class Solution(object):
   def solve(self, s):
      stack = [-1]
      ans = 0
      for i in range(len(s)):
         if s[i] == "(":
            stack.append(i)
         else:
            if stack and stack[-1]!=-1 and s[stack[-1]] == "(":
               stack.pop()
               ans = max(ans,i - stack[-1])
            else:
               stack.append(i)
      return ans
ob = Solution()
print(ob.solve("))(())())"))

入力

"))(())())"

出力

6