[record of question brushing] 20. Valid brackets

One 、 Title Description

source ：

Power button （LeetCode）

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 <= 104

• s  Brackets only  '()[]{}'  form

II. Train of thought analysis

Stack to solve the problem

In this topic , When we traverse , Each left parenthesis , Should correspond to a corresponding right parenthesis , And the left parenthesis appearing after it should be matched first , This heel stack  

First in, then out

  It's very similar .

• When encountering the left parenthesis , Push

• When you encounter the right parenthesis , Take out the top bracket

• Judge out brackets   Whether it is consistent with the type of right parenthesis , atypism , Go straight back to
  false

• If there are no left parentheses in the stack , And go straight back to  
  false

• When all strings are traversed

• The stack is empty. , It means that all parentheses are closed

• Stack is not empty. , Note that there are parentheses that do not match the closure

• When it comes to matching , The string length must be even , Otherwise, it will not match , Go straight back to  
  false

• For easy matching , We can use a hash table to store every kind of parenthesis . The key is a right parenthesis , Values are left parentheses of the same type .

3、 ... and 、 Code implementation

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

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


Complexity analysis

Time complexity ：

, among  

n

  Is string  

s

  The length of .

Spatial complexity ： The complexity is &nbsp;

, Use the space of hash table

Running results

summary

There are some problems , We can use data structures with similar characteristics to deal with , It can help us solve problems faster .