デイリーアルゴリズム: 有効な括弧

[[420388]]

'('、')'、'{'、'}'、'['、']' のみで構成される文字列が与えられた場合、その文字列が有効かどうかを判断します。

有効な文字列は次の要件を満たしている必要があります。

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

空の文字列は有効な文字列とみなされることに注意してください。

例1:

入力: "()"  
出力: true  

例2:

入力: "()[]{}"  
出力: true  

例3:

入力: "(]"  
出力: false  

例4:

入力: "(]"  
出力: false  

例5:

入力: "([)]"  
出力: false  

答え: スタック構造を使用する

解決策: 文字列内の文字を 1 つずつスタックにプッシュし、文字を走査して 1 つずつ判断します。

• まず要素が{、(、[であるかどうかを判断し、それを直接スタックにプッシュします。
• それ以外の場合、文字は }、)、] のいずれかであり、文字列が有効であれば、要素はスタックの先頭と一致する必要があります。たとえば、スタックに ({) があり、次に走査される要素が ) である場合、現在の要素シーケンスは ({) であり、これは有効ではありません。したがって、スタックの先頭要素との一致は失敗し、文字列が無効であることを示す false が直接返されます。

トラバーサルが完了すると、一致した文字はすべて一致し、スタックからポップアウトされます。この時点でスタックが空であれば、文字列は有効です。スタックが空でない場合は、文字列に一致しない文字があり、文字列が無効であることを意味します。

理解を助けるために絵を描きます:

コード実装:

 const isValid =関数(s) {
    マップ = {
 '{' : '}' 、
 '(' : ')' 、
 '[' : ']'  
    }
    スタック = []
 ( i = 0 とします; i < s.length; i++) {
        if(map[s[i]]) {
            スタックをプッシュする(s[i])
        }そうでない場合、s[i] !== map[stack.pop()]){
戻る 間違い 
        }
    }
スタックの長さを 0 で返す
};

時間計算量: O(n)

空間計算量: O(n)