Question

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

Tag

String
Stack

My Idea

If the input is an opening bracket, put it in the stack;
If the input is a closing bracket, compare it with the top element of the stack.

Highlights

• Push the reverse element of the input into the stack, so we can simply compare the new element and the topmost element from the stack.
• set the return value of the function isValid as return not stack but simply return True. Because the main idea of this code is to pop the elements that have been matched. so we have to make sure that when there is no new character in string s, there are no more characters in the stack. if it has, that means the parentheses are not valid, need to return False. This kind of code can simply avoid the mistake when the test case is like "[".

My Code

class Solution:
    def isValid(self, s: str) -> bool:
        # Build a stack
        stack = []
        for c in s:
            if c == "(":
                stack.append(")")
            elif c == "[":
                stack.append("]")
            elif c == "{":
                stack.append("}")
            else:
                if not stack:
                    return False
                if not c == stack.pop():
                    return False
        # Make sure the stack is empty. input: "["            
        return not stack

Better Idea

• Using Hash map for keeping track of mappings. This keeps the code very clean. Also makes adding more types of parenthesis easier.

Better Code

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        mapping = {')':'(', ']':'[', '}':'{'}
        for c in s:
            # if c is a closing bracket
            if c in mapping:
                # if the stack is empty, assign a dummy value '#'
                TopElement = stack.pop() if stack else '#'
                if mapping[c] != TopElement:
                    return False
            else: stack.append(c)
        return not stack

Summary and To be done

This is a question that was previously demonstrated in class, I was always thinking that maybe I will start with Two Sum. :smile: It turns out that not all the problems in the LeetCode are hard, and it's interesting to think and solve the problems.

This problem takes me two hours, that's crazy. I did a lot of tests when I am solving this. I am not familiar with python anymore, I even didn't know how to write annotation in Python. :smile: Delightfully, I know how to write annotation finally, and hopefully, I can be a data structure and algorithm master.

Python has a lot of advanced new features (like stack can just build like a list), sometimes these advanced features will make the problem been solved quickly as hell. However, solving problems like this will make me ignore tons of details.

So I am thinking that I will use Python to get through the initial stage of my journey of the LeetCode, to get familiar with data structures and algorithms. And then, maybe I'll try to use C++ or Java to solve those advanced problems.