Python Algorithm Q20

Q20 Valid Parentheses

---

Q

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.

Sample Input

Input: s = “()”
Output: true

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

Input: s = “(]”
Output: false

Constraints

• 1 <= s.length <= 10⁴
• s consists of parentheses only '()[]{}'.

1. My Solution <- Given Solution

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []

        #keys ) } ], values ( { [
        table = {')':'(', '}':'{', ']':'['}
        
        for char in s:
            if char not in table: #table "keys"
                stack.append(char)

            #if only once wrong, return false & if stack is empty
            # when close parantheses appears first, IN TABLE but STACK IS EMPTY
            elif not stack or stack.pop() != table[char]:
                return False 

        return len(stack) == 0 #check if the stack is empty

# for the test
a = Solution()
s = "()[]"
if a.isValid(s):
    print("True")
else:
    print("False")

We have to remind the conditions that bracket become valid. Bracket follows stack-structure, Last in First Out. Therefore last open-bracket have to be closed at first. We can make this with the stack.

1. Table consist of close-bracket(as a key) : open-bracket(as a value).
2. Repeat each letter in the input string.
3. Each loop, check input with if-statement.
   3-1. if~ : Check whether the letter is in the table keys(close-bracket). When open-bracket comes in, of course it is not in the keys, so it appended to the stack.
   3-2. elif~ : check if stack is empty or not, and pair matches or not. When close-bracket comes, this bracket passes if then comes to elif. Compare the item that pops from the stack with “table[close-bracket]”, which returns the pair open-bracket. If not matches, immediately returns false.
   3-3. not stack filters the case when close-bracket comes first. When close-bracket comes, this passes if (since it is in the keys). So stack doesn’t have any element. This fulfills elif, so return false.

Overall Review

Experiencing new concepts always makes me confused, but on the other hand I’m looking forward to learn the concept that I’d never learnt. Stack itself is surely easy concept, but implementing stack with python or other language is not that easy…