Leetcode-20. Valid parentheses (day5)

Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit series activities – click on the task to see the details of the activities.

One, foreword

👨🎓 Author: Bug Bacteria

✏️ blog: CSDN, Nuggets, etc

💌 public account: Magic House of the Circle of the Apes

🚫 special statement: original is not easy, reprint please attach the original source link and this article statement, thank you for your cooperation.

🙏 Copyright notice: part of the text or pictures in the article may come from the Internet or Baidu Encyclopedia, if there is infringement, please contact bug bacteria processing.

Hello, little friends, I am bug bacteria 👀. Gold three silver four, brush the month again. So whether you’re looking for a career change or a career change, get your act together and do the right thing 👣. So, quickly follow the pace of bug bacteria roll up ⏰, become strong from this moment ➕🧈.

In the process of reviewing articles, if you think the articles are helpful to you at all, please don’t be too mean with your likes and bravely light up the articles 👍. Your likes (collect ⭐️+ pay attention to 👨 port + message board) are the best encouragement and support for bugs on my creation path. Time does not abandon 🏃🏻♀️, nuggets stop 💕, cheer up 🏻

Ii. Title Description:

Topic:

Given a only include a ‘(‘,’) ‘, ‘{‘,’} ‘, ‘/’, ‘ ‘the string s, determine whether a string is effective.

A valid string must meet the following requirements: The left parenthesis must be closed with the same type of the right parenthesis. The left parentheses must be closed in the correct order.

Please see the following examples:

Example 1:

Input: s = "()" output: trueCopy the code

Example 2:

Input: s = "()[]{}" Output: trueCopy the code

Example 3:

Input: s = "(]" Output: falseCopy the code

Example 4:

Input: s = "([)]" Output: falseCopy the code

Example 5:

Input: s = "{[]}" Output: trueCopy the code

LeetCode: ⭐⭐

Iii. Analysis of Ideas:

So when I look at this, it kind of gives me the illusion that I’m going to count the number of parentheses and the number of parentheses, and then I’m going to say that each of them is the same, so I have valid parentheses. In fact, no, such as [{]}, obviously all the left and right parentheses are equal, but not valid, because valid depends on the position.

Therefore, when I carefully observe, I found a feature, which is very consistent with the stack first in last out. That is, if the left parenthesis is pushed onto the stack, the left parenthesis at the top of the stack will be pushed off the stack when the close parenthesis is encountered. Therefore, the stack is still empty after all the parentheses are traversed, which shows that the parentheses are valid.

So the idea is to iterate over the string STR and divide it up

When an open parenthesis is encountered, it is expected to be closed by a close parenthesis of the same type in subsequent traversals. Since the left parenthesis encountered later is closed first, we can place the left parenthesis at the top of the stack.
When we encounter a close parenthesis, we need to close an open parenthesis of the same type. At this point, we can pull out the left parentheses at the top of the stack and determine if they are of the same type. If they are not of the same type, or there are no open parentheses on the stack, then the string s is invalid and returns false.
Note that the length of the valid string must be even. If the length is odd, return false without further traversal.

Animation demo:

The above animation is a process to verify whether the brackets are valid based on the characteristics of the stack. Finally, if the stack is empty, the brackets are valid; if the stack is not empty, the brackets are invalid.

Iv. Algorithm implementation:

Stack assist method _AC code

The specific algorithm code is as follows:

class Solution { public boolean isValid(String s) { //1. Is null or an odd number of skip the if (s.i sEmpty () | | s.l ength (% 2) = = 1) {return false. } //2. Create secondary Stack<Character> Stack = new Stack<>(); / / 3. Traversal for (char c: s.t oCharArray ()) {if (c = = '(') {stack. Push (')); }else if(c == '['){ stack.push(']'); }else if(c == '{'){ stack.push('}'); }else if(stack.isEmpty() || c ! = stack.pop()){ return false; }} //4. Return stack.isempty (); }}Copy the code

V. Summary:

The screenshot of stack assist leetcode submission result is as follows:

Complexity analysis:

Time complexity: O(n), where n is the length of string S.
Space complexity: O(N +∣ σ ∣) where σ stands for character set, the string in this case contains only six brackets, ∣ σ ∣=6. The number of characters in the stack is O(n), and the space used by the hash table is O(sigma ∣), which adds up to the total space complexity.

If you have some basic knowledge of the stack, then you can solve the problem easily. The main point is to use the characteristics of the first and last stack to solve the problem. Furthermore, there are thousands of ways to solve the problem, friends, if you have a better idea or idea to solve the problem, please let me know in the comment section. We can learn from each other together, so that we can grow faster.

Well, that’s all for this episode and I’ll see you next time.

Six, the previous recommendation:

Leetcode -1. Sum of two numbers
Leetcode – 9. Palindrome
Leetcode -13. Roman numeral to integer
Leetcode -14. The longest public prefix

. .

Vii. End of article:

If you want to learn more, check out bug Bug’s LeetCode Problem of the Day column! Take you to brush together. One person may feel very tired and difficult to persist in brushing, but a group of people will think it is a meaningful thing to brush, urge and encourage each other, and become stronger together.

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

☘️ Be who you want to be, there is no time limit, you can start whenever you want,

🍀 You can change from now on, you can also stay the same, this thing, there are no rules to speak of, you can live the most wonderful yourself.