LeetCode Day 11 Stack and queue(2/3)

The second day of practice about stack and queue

Question 1

20. Valid Parentheses

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. Every close bracket has a corresponding open bracket of the same type.

The question stem is easy to understand, and to do it, it can also be done in a stupid way, by giving the left and right brackets an array count, and finally seeing if there are any unmatched arrays left. I did a bit of work and found that it was not well thought out, because the question stem requires that Open brackets must be closed in the correct order, so you can’t check the order!

After reading the parse, I realised that this question is a classic one that can be solved using a stack. As well, when writing the code, envision all the scenarios that will occur in this question ahead of time, and consider them thoroughly before writing:

1. the left bracket is redundant, and the match is incomplete

2. left and right brackets are not redundant, but there is a type inconsistency

3. the right bracket is redundant and the match is incomplete.

The corresponding solutions:

The first case: the string has been traversed, but the stack is not empty, indicating that there is a corresponding left bracket does not have a right bracket to match, so return false.

The second case: during the process of traversing the string to match, it is found that there is no character to match in the stack. So return false

The third case: traversing the string matching process, the stack is already empty, there is no matching character, that means the right bracket did not find the corresponding left bracket return false

There are also some tricks, when matching the left bracket, the right bracket into the stack first, you just need to compare the current element and the top of the stack is not equal, than the left bracket into the stack first code implementation is much simpler!

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

Question 2

1047. Remove All Adjacent Duplicates In String

You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them.

We repeatedly make duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made. It can be proven that the answer is unique.

At first glance, it looks like a while loop structure that removes duplicates until it can’t be removed. However, when it comes to removing duplicates, the idea is again like the matching bracket elimination in the previous question, which can be solved by using the stack. When traversing the string, if you hit a duplicate item, you pop it up, and what remains on the stack at the end is the result.

class Solution:
    def removeDuplicates(self, s: str) -> str:
        res = list()
        for item in s:
            if res and res[-1] == item:
                res.pop()
            else:
                res.append(item)
        return "".join(res)

Question 3

150. Evaluate Reverse Polish Notation

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

• The valid operators are '+', '-', '*', and '/'.
• Each operand may be an integer or another expression.
• The division between two integers always truncates toward zero.
• There will not be any division by zero.
• The input represents a valid arithmetic expression in a reverse polish notation.
• The answer and all the intermediate calculations can be represented in a 32-bit integer.

This question seemed confusing at first, but by imagining an equation as a binary tree, which is what we are accustomed to in our daily reading is the medial representation, and the suffix representation of this RPN is a backward traversal of a binary tree.

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for i in tokens:
            if i not in ['+','-','*' ,'/']:
                stack.append(i)
            else:
                first_num = stack.pop()
                second_num = stack.pop()
                stack.append(int(eval(f'{second_num} {i} {first_num}')))
 
        return int(stack.pop())