NeetCodeのSolutionを書いていく #
Valid Parentheses #
https://neetcode.io/problems/validate-parentheses
neetcode.io
() {} [] に囲まれている文字列を有効とする。
- 全てのカッコは同じ種類のカッコで閉じられている必要がある。
- カッコは正しい順番で閉じられる必要がある。
- 全ての閉じるカッコは適切な開けるカッコが必要である。
Stackという商の問題なので、FILOのStackに積んでいけばいいってことだよね。 ‘(’ ならば ‘)’ を、’{’ ならば ‘}’ を ‘[’ ならば ‘]‘をスタックに積んで次のカッコはそれである必要がある。
class Solution:
def isValid(self, s: str) -> bool:
parentheses = {"(": ")", "{": "}", "[": "]"}
open = ["(", "{", "["]
close = [")", "}", "]"]
stack: list[str] = []
for c in s:
if c in open:
stack.append(parentheses[c])
elif c in close:
if len(stack) == 0:
return False
if stack[-1] == c:
stack.pop()
else:
return False
else:
pass
return len(stack) == 0
あと、開くカッコだけの場合、閉じるカッコが最初に来る場合、もケアしないとだめだった。 開くカッコだけのケアのためには、最後にスタックが0になることを確認。 閉じるカッコが最初に来るのはスタックに何も積まれていないのに閉じるカッコが来たかの確認で実施。
解法に記載されたアルゴリズムが面白い。
class Solution:
def isValid(self, s: str) -> bool:
while '()' in s or '{}' in s or '[]' in s:
s = s.replace('()', '')
s = s.replace('{}', '')
s = s.replace('[]', '')
return s == ''
これって文字列にはカッコしか含まれていないってことなんか。 たしかにだとすればこれで行けるか。 問題を正確に読むことの(書くこと?)の難しさよ。
Reply by Email