20. Valid Parentheses

LeetCodeにあった問題です。()のように一組の括弧がすべての組み合わせに対して正しい順序で成立していれば正解。({[]})のような組み合わせはOKですが、({)}のような組み合わせはダメ、というものです。ちなみに初見では解けませんでした。Easyで結構初見で解けない問題があるのですが、本当にEasyなのかとても気になってくる。

leetcode.com

最初の自分の考察

(という文字列を見つけたとき、隣に)が来ていれば正当（valid）なのではと考えていたのですが、そうすると({})のような組み合わせの際に撃沈します。

解き方

この手の問題ではスタックが利用できます。開始の括弧、つまり(、{、[が来た際にスタックに積んでおき、閉じ括弧が来たらスタックからpopして対応する括弧であればvalidとするという解法です。

たとえば、おそらく一番複雑な部類になるであろう ({[]}) について考察してみると、

1. ( が来る→スタックに積む。スタックの状態: (
2. {が来る→スタックに積む。スタックの状態: {、(
3. [が来る→スタックに積む。スタックの状態: [、{、(
4. ]が来る→スタックからpop。popした値は[。]は[に対応するので、valid
5. }が来る→スタックからpop。popした値は{。}は{に対応するので、valid
6. )が来る→スタックからpop。popした値は(。)は(に対応するので、valid

といった感じで、綺麗に問題を解けます。最初解法を見たときおもしろいなと思いました。

下記に Python による解法を示しておきます。

# (, {, [ のどれかだった場合（"開始"とする）、スタックに積んでおく。
# "開始"でなかった場合、スタックに積んだものを順に上からpopしていき、一致していなかったらFalseを返す。

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        
        for char in s:
            if char in ["(", "{", "["]:
                stack.append(char)
            else:
                if not stack:
                    return False
                
                curr = stack.pop()
                
                if curr == "(":
                    if char != ")":
                        return False
                if curr == "{":
                    if char != "}":
                        return False
                if curr == "[":
                    if char != "]":
                        return False
                
        if stack:
            return False
        
        return True

時間計算量は O(n) です。for char in s というループ一つですべてが完結するためです。s の長さだけループが必要な回数が増えるだけ。

空間計算量は O(n) です。これはスタックを実質外部のメモリとして使用するためでしょう。s の長さだけ積まれるスタックの量が増えるので、この計算量になります。