Stack and queue - 20. Valid parentheses

1 Title Description

Given one only includes ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ String s , Determines whether the string is valid .

Valid string needs to meet ：

Opening parentheses must be closed with closing parentheses of the same type .
The left parenthesis must be closed in the correct order .

2 Title Example

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 ：true

3 Topic tips

1 <= s.length <= 104
s Brackets only ‘()[]{}’ form

4 Ideas

To judge the validity of parentheses, you can use 「 Stack 」 this — Data structure to solve .
We iterate over a given string s. When we encounter an open parenthesis , We will expect that in the subsequent traversal , There is a closing bracket of the same type to close it . Because the left bracket encountered after must be closed first , So we can put the left bracket at the top of the stack . When we encounter a closing bracket , We need to close an open parenthesis of the same type . here , We can take out the left parentheses at the top of the stack and judge whether they are the same type of parentheses . If not of the same type , Or there is no left parenthesis in stack , So the string s Invalid , return False. To quickly determine the type of parentheses , We can use a hash table to store every — Kind bracket . The key of the hash table is the right parenthesis , Values are left parentheses of the same type .
After traversing the knot , If there is no left parenthesis in the stack , Note that we will string s All left parentheses in are closed , return True, Otherwise return to False.
Notice the length of the valid string — Set as even number , So if the length of the string is odd , We can go straight back False, Omit the subsequent traversal judgment process .

5 My answer

Method 1 ：

class Solution {
    
    public boolean isValid(String s) {
    
        int n = s.length();
        if (n % 2 == 1) {
    
            return false;
        }

        Map<Character, Character> pairs = new HashMap<Character, Character>() {
    {
    
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        Deque<Character> stack = new LinkedList<Character>();
        for (int i = 0; i < n; i++) {
    
            char ch = s.charAt(i);
            if (pairs.containsKey(ch)) {
    
                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
    
                    return false;
                }
                stack.pop();
            } else {
    
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
}