【LeetCode】20. Valid Parentheses 解答・解説【Python】

この記事は約2分で読めます。

 

問題

原文

Given a string s containing just the characters '('')''{''}''[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.
  3. Every close bracket has a corresponding open bracket of the same type.

内容

以下の括弧を含む文字列型変数sが与えられる。入力された文字列が正しいか判断してください。

 '('')''{''}''[' and ']'

入力される文字列は以下の条件を満たせば正しいと判断できます。

  1. 開始カッコは同じ種類の終了カッコでなければならない
  2. 開始カッコはただしい順序で閉じられなければならない
  3. 全ての終了カッコは同じ種類の開始カッコでなければならない

 

※正しくない可能性があります。

 

方針

・変数s内の文字列を全探索

・開始カッコならスタックに入れる

・スタック内に文字列がない、または終了カッコだった場合は以下に分岐

→stackの要素が1つ以上あり、さらに文字列がスタックの最後(一番上)の要素と対応するカッコの場合はスタックの最後の要素を取り出す。そうでなければFalseを返す

・変数s内の文字列の探索が終了後、スタックに要素が残っていればFalse、残っていなければTrueを返す

解答

解答1

補足・参考・感想

スタックを使う問題のようでした。実際の面接では英語で行うことに加えて、これ以外の解法がないか、別解と今回の解法のメリットとデメリットを比較して相談しながら解法を決めた上でミスなく早くコーディングを行うことが求められるのだろうなと思います。

スタックを書いてみたのは初めてだったので、一般的に今回のような書き方をするのか、他にも何か決まった書き方のようなものがあるのか、勉強してみたいと思います。

 

コメント