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

This article mainly explains "how to judge whether the parentheses are valid". Friends who are interested might as well take a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn "how to judge whether the parentheses are valid".

Title

Given a string 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.

Note that an empty string can be considered a valid string.

Example 1:

Input: () output: true

Example 2:

Input: "() [] {}" output: true

Example 3:

Input: "(]" output: false

Example 4:

Input: ([)] "output: false

Example 5:

Input: "{[]}" output: true LeetCode address: https://leetcode-cn.com/problems/valid-parentheses

Problem-solving ideas

This question is to verify the symmetry of parentheses. For example, the string "([{}])" is correct and should return true, while the string "([{})]" is wrong and should return false.

As can be seen from the above topic, parentheses are divided into three categories: parentheses, square braces and curly braces, so we can make use of the first-in-and-out feature of the stack to put all the left parentheses ("(", "[", "{") into the stack first, and then when you encounter the right parenthesis, let it match the elements at the top of the stack. For example, if the top of the stack is "("), it means the match is successful. The element at the top of the stack goes out of the stack and then continues the process of string loop, and if there is a matching error, it will directly return false.

Suppose we want to match the string "([])" is it legal? Then the execution process is like this.

First encounter the left parenthesis and enter the stack first:

Then there is the left parenthesis, which continues into the stack:

Then, with the left parenthesis, continue into the stack:

Next is the right parenthesis, which matches the top element of the stack. "[]" is a pair of legal parentheses that successfully match the top element of the stack:

Next, there is the right parenthesis, which matches the top element of the stack. "()" is a pair of legal parentheses that successfully match the top element of the stack:

Next, there is the right parenthesis, which matches the top element of the stack. "()" is a pair of legal parentheses that successfully match the top element of the stack:

When the string loop ends and the stack is empty, the parenthesis matching of the string is proved to be valid, and the final effect is as follows:

Then we will use the code to implement the whole process.

Implementation code one

Public boolean isValid (String s) {int slen = s.length (); / / length of parentheses if (slen% 2 = = 1) {/ / parentheses do not appear in pairs and directly return false return false;} / / store all contrastive parentheses in map with Map map = new HashMap (); map.put (')','(') Map.put ('}','{'); map.put (']','['); / / define the stack for accessing parentheses (auxiliary comparison) Stack stack = new Stack (); for (int I = 0; I < slen; iTunes +) {/ / loop all characters char c = s.charAt (I) If (map.containsKey (c)) {/ / is the parenthesis on the right, such as')','} 'and other if (stack.isEmpty () | | stack.peek ()! = map.get (c)) {/ / stack is empty or parentheses do not match return false;} stack.pop () / / is a pair of parentheses, execute else {/ / left parenthesis, directly into the stack stack.push (c);}} return stack.isEmpty ();}

We submit the code in LeetCode, and the execution result is as follows:

Code parsing

The map set of the above code is used to define the matching rules of parentheses. For example, the matching value corresponding to "(", "]" is "[", etc.), and then we loop the string to be verified. When we encounter the left parenthesis and enter the stack directly, we encounter the right parenthesis to match the element at the top of the stack. When the whole string loop ends, if the stack is empty, the parenthesis of the string is legal.

Complexity analysis

Time complexity: O (n), traversing the entire string. Space complexity: O (n).

Implementation code two

In addition to using the stack, we can also use the replace method in Java to cyclically remove parentheses in a string, such as replacing "()" or "[]" or "{}" with an empty loop. Finally, if the string is empty after execution, the parentheses in the string are legal. The specific implementation code is as follows:

Public boolean isValid (String s) {int len; do {len = s.length (); / / eliminate the symbol s = s.replace ("()", "). Replace (" [] ","). Replace ("{}", ");} while (len! = s.length ()); / / can no longer be replaced. The replace method does not replace any characters return s.length () = = 0;}

We submit the code in LeetCode, and the execution result is as follows:

From the running results, the difference in execution efficiency between the two is still very obvious:

At this point, I believe you have a deeper understanding of "how to judge whether the parentheses are valid". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

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.