有効な括弧

指示

文字 '(', ')', '{', '}', '[' および ']' のみを含む文字列 s を指定して、入力文字列が有効かどうかを判断します.

次の場合、入力文字列は有効です.

開き括弧は、同じタイプの括弧で閉じる必要があります.
左括弧は正しい順序で閉じる必要があります.

例

Input: s = "()[]{}"
Output: true

Input: s = "(]"
Output: false

アプローチ

この問題では、主に遭遇した最新の括弧に関心があり、それが閉じ括弧である場合、以前に遭遇した開き括弧に一致させます.閉じ括弧の前に開き括弧がない場合、文字列は有効な括弧ではありません.

最新のキャラクターに関心があるため、後入れ先出し (LIFO) 動作を実装するスタック データ構造を使用できます.
したがって、スタックに入る最後のアイテムが最初に削除されます.

そのため、開き括弧をプッシュし、対応する閉じ括弧に遭遇すると、それ (開き括弧) をスタックからポップします.

有効な括弧文字列 s の場合、最終結果は空のスタックになります.スタックが空でない場合、s は有効な括弧ではありません.

Python 実装

壊す

スタックを初期化して、

から追加およびポップします

閉じがキーで開きが値である括弧の辞書を初期化します.

指定された文字列をループします.文字列の要素が辞書のキーにある場合、スタックが空かどうかを確認します
そして、stack[-1] の要素、つまり最新の要素が dict[i] の要素と等しい場合、このブラケットをスタックから削除します.
注: スタックが空の場合、有効な文字列は閉じ括弧で開始できないため、False を返します.

上記の条件が満たされない場合、すぐに false を返します
それ以外の場合は、スタックに追加します.これは、文字列内の要素が開き括弧であることを意味するためです.

コード

def isValid(self, s):        
    parentheses = {'}': '{', ']': '[', ')': '('}
    stack = []
     for i in s:
         if i in parentheses:
            if stack and stack[-1] == parentheses[i]:
               stack.pop()
             else:
                 return False
         else:
             stack.append(i)
     return not stack

時間の複雑さ

の上)
アルゴリズムは、入力が増加するにつれて線形にスケーリングします.

スペースの複雑さ

スペースの複雑さは O(n) です.これは、すべての要素が開き括弧であるという最悪のシナリオでは、n 個の要素をスタックに格納する必要があるためです.