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

This article introduces the relevant knowledge of "how to judge the valid parentheses of LeetCode". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

A valid parenthesis description of the topic

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

A valid string must satisfy:

The left parenthesis must be closed with the same type of closing parenthesis

The left parenthesis 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

Example 5:

Input: s = "{[]}" output: trueSolution solution

What are the ideas for judging valid parentheses?

If the length of the s string is odd, it must not be closed, and you can return false directly.

Cache mapping is established. KEY is left parenthesis and VALUE is right parenthesis.

By making use of the first-in-first-out characteristic of the stack, it is very suitable for our idea of this question. If we encounter the left parenthesis ([({) entering the stack, making the right parenthesis (}]) judgment, the left parenthesis at the top of the corresponding stack will be out of the stack. Finally, the data in the stack is empty after traversing the stack.

CODEclass Solution {public boolean isValid (String s) {int length = s.length (); / / it is impossible to close the cache mapping of if (length%2==1) {return false;} / / the cache mapping between left and right parentheses Map map = new HashMap (); map.put ('(',)'); map.put ('[',']') Map.put ('{','}'); Stack stack = new Stack (); for (int I = 0; I < length; iTunes +) {char c = s.charAt (I); / / whether it is left parenthesis if (map.containsKey (c)) {stack.push (c) } else {/ / if it is a closing parenthesis and the stack depth is 0, the current string is a close parenthesis string, which can be returned directly to false, such as')'}'}']'())}]'if (stack.size () = = 0) {return false } / / pops up the stack and gets it from the cache. If the corresponding closing parenthesis matches the current string, whether it is equal or not, it returns false if (! map.get (stack.pop ()) .equals (c)) {return false } / / finally judge the stack depth. If it is empty, it means the return stack.empty ();}} complexity

Time complexity: O (n), where n is the length of the string s

Result

Execution time: 2 ms, beating 76.91% of users in all Java submissions

Memory consumption: 36.8 MB, beating 25.12% of all Java submissions

I have walked on the silver plains and fished in the river of grass. This land knows me, and if we are not strong, we will perish.

This is the end of the content of "how to judge the valid parentheses of LeetCode". Thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

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.