Leetcode 20. Valid Parentheses

Problem

対応する括弧が適切に開かれて閉じられているかを判定する問題です。

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

InputとOutputの例は次になります。

Input: s = "()[]{}"
Output: true

Input: s = "(]"
Output: false

Key Idea

Stackを利用します。対応する括弧が適切に開かれて閉じられているかを確認するために、Stackに開始括弧をプッシュし、終了括弧が出現したときに最後に開いた括弧と比較します。

Approach #1 Stack

手続き的で冗長な書き方ではありますが、Approach #2の前準備として記載します。PythonではlistをStackとして利用することができます。pushはlist.append()、peek は、list[-1]、popはlist.pop() で実装できます。参考までに、実務においては collections.deque を使うと、listよりも高速なスタック操作が可能です。

class Solution:
    def isValid(self, s: str) -> bool:

        stack = []
        for char in s:
            if s[i] in [')','}',']']:
                if len(stack) == 0:
                    return False

                if char == ')':
                    if stack[-1] == '(':
                        stack.pop()
                    else:                        
                        return False

                if char == '}':
                    if stack[-1] == '{':
                        stack.pop()
                    else:                        
                        return False

                if char == ']':
                    if stack[-1] == '[':
                        stack.pop()
                    else:                        
                        return False
            else:
                stack.append(char)
                
        if len(stack) == 0:
            return True
        else:
            return False

Approach #2 Stack + Hashmap

括弧の種類の違いによる処理が冗長なので、Hashmapを使って、Approach #0をよりスッキリさせています。

class Solution:
    def isValid(self, s: str) -> bool:

        stack = []
        hashmap = {')':'(', '}':'{', ']':'['}
        for char in s:
            if char in hashmap:
                if len(stack) == 0:
                    return False

                if stack[-1] == hashmap[char]:
                    stack.pop()
                else:                        
                    return False
            else:
                stack.append(char)
                
        if len(stack) == 0:
            return True
        else:
            return False
                
                
            

この解法では、計算量は下記の様になります。

• Time complexity: O(n)。すべての文字を1文字ずつscanします。Scan中にstackにpushとpopを行うのは最悪の場合でも文字列の長さに比例します。

• Space complexity: O(n)。最悪の場合、すべての文字が開き括弧である場合にスタックにすべての文字が追加される可能性があります。

Reference