[leetcode] 20. Valid brackets

20、 Valid parenthesis

subject ：

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 .

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

Tips ：

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

Their thinking ：

1. First, if the string can form valid parentheses , Then the length must be even
2. We can iterate through strings , If the left bracket is encountered, it will be temporarily stored , Expect a closing parenthesis to match it
3. If a closing bracket is encountered, check whether it matches the latest temporary bracket .
4. This is consistent with the first in and last out characteristics of stack data structure . So we can prepare a stack to store bracket pairs
5. When traversing a string , If you encounter an open bracket, put it on the stack , If the right bracket is encountered, judge whether the right bracket can match the top element of the stack , At the end of the loop, it is also necessary to determine whether the stack is empty , If it's not empty , Is not a string matching valid parentheses

Complexity analysis ：

Time complexity ：O(n), among n Is string s The length of .

Spatial complexity ：O(n+∣Σ∣), among Σ Represents the character set , The string in this question only contains 6 Kind bracket ,∣Σ∣=6. The number of characters in the stack is O(n), The space used by the hash table is O(∣Σ∣), Add to get the total space complexity .

Specific code ：

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();
    }
}