LeetCode学習メモ: 20. Valid Parentheses

昨年からコンピュータサイエンスの自己学習を始めていて、leetcodeやらrecursionやらudemyに取り組んでいる。インプットは継続的に行なっているのだが、アウトプットの機会がほぼなく、自分の中で腹落ちして理解するために学習ログを残すこととする。

概要

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

An input string is valid if:

Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order.

引用元: https://leetcode.com/problems/valid-parentheses/

方針

stackとhashmapを復習できる良問。 事前に「閉じる方のbracket」をkeyとして、「始まる方のbracket」をvalueとしたhashmapを用意する。 また、stackを用意して、stackの中にcharactersをpushしていく。

givenされたcharactersを展開して、「閉じる方のbracket」が出てきたとき、stackからpopした値が「始まる方のbracket」であればTrue、そうでなければFalseを返す。

コード

def isParenthesesValid(characters):
    stack = []
    hashmap = {")": "(", "}": "{", "]": "["}

    for c in characters:
        if c in hashmap:
            top_element = stack.pop() if stack else ''
            if top_element != hashmap[c]:
                return False
        else: stack.append(c)
    return True