Shulou(Shulou.com)06/01 Report--

Xiaobian to share with you how LeetCode judges effective brackets, I believe most people still do not know how, so share this article for your reference, I hope you have a lot of harvest after reading this article, let's go to understand it together!

Title Description:

Given a string s containing only '(',')','{','}','[',']', determine whether the string is valid.

Valid strings must satisfy:

The left parenthesis must be closed with a right parenthesis of the same type.

The left brackets must be closed in the correct order.

Example 1:

Input: s = "()"

Output: true

Example 2:

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

Output: true

Example 3:

Input: s = "(]"

Output: false

Example 4:

Input: s = "([)]"

Output: false

Thought analysis: implement it with stack.

The validity of parentheses can be determined using the data structure stack.

We traverse a given string ss, and when we encounter a left parenthesis, we expect a right parenthesis of the same type to close it in subsequent iterations. Since the left parenthesis encountered later has to be closed first, we can put this left parenthesis at the top of the stack.

When we encounter a right parenthesis, we need to close a left parenthesis of the same type. At this point, we can remove the left parenthesis at the top of the stack and determine whether they are the same type of parenthesis. If it is not the same type, or if there is no left parenthesis in the stack, then the string s is invalid and returns False. To quickly determine the type of parenthesis, we can use a hash map to store each parenthesis. The key of the hash map is a right parenthesis and the value is a left parenthesis of the same type.

At the end of the traversal, if there is no left parenthesis in the stack, we close all the left parenthesis in the string s and return True, otherwise we return False.

Note that valid strings must be even in length, so if the length of the string is odd, we can return False directly, eliminating the subsequent traversal process.

Python implementation class Solution:

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

stack=[] #Set up a list and use it as a stack.

dic={')':'(','}':'{',']':'['} #Use dictionary to store parenthesis, and right parenthesis is key, left parenthesis is value

for char in s:

if char in dic.values(): #Left parenthesis is on the stack

stack.append(char)

elif char in dic.keys(): #If there is a right parenthesis, compare it,

if stack==[] or dic[char] != stack.pop():

return False

else:

return False #No longer input directly output errors in the dictionary

return stack==[]

Java implementation: class Solution {

public boolean isValid(String s) {

int len=s.length();

if(len%2==1){

return false;

}

Map map=new HashMap(){

{

put(')','(');

put(']','[');

put('}','{');

}

};

Stack stack=new Stack();

for(int i=0;i

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.