LeetCode one question of the day, valid parentheses

The title

Valid parentheses

Leetcode-cn.com/problems/va…

The public account “Java Programming Notes” record Java learning daily, share learning road dribs and drabs, from entry to give up, welcome to pay attention to

describe

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

A valid string must meet the following requirements:

• Left parenthesisMust be usedThe same typetheRight parenthesisclosed
• Left parenthesisHave to beCorrect orderclosed

Example 1:

Enter: s ="()"Output:true

Copy the code

Example 2:

Enter: s ="[the] {} ()"Output:true
Copy the code

Example 3:

Enter: s ="(]"Output:false
Copy the code

Example 4:

Enter: s ="([]"Output:false
Copy the code

Example 5:

Enter: s ="{[]}"Output:true
Copy the code

Solution

solution

Their thinking

What are the ideas for determining valid parentheses?

• ifS a stringFor the length of theAn odd number, it must not be closed, you can directly return false
• Create a cache map,KEYIs the left parenthesis,VALUEFor the right parenthesis
• Through the use ofThe stack 先Into theafterOut of theIf you encounter an open parenthesis ([({), before closing parenthesis (}])) will correspond when judgingTo the top of the stackOpen parenthesis out of the stack, the last traversalData in the stackforempty

CODE

class Solution {
    public boolean isValid(String s) {
        int length  = s.length();
        // Odd numbers cannot be closed
        if(length%2= =1) {return false;
        }
      	// Cache mapping between open and close parentheses
        Map<Character,Character> map = new HashMap<>();
        map.put('('.') ');
        map.put('['.'] ');
        map.put('{'.'} ');
        
        Stack<Character> stack = new Stack();
        for(int i = 0 ; i < length ; i++){
            char c =  s.charAt(i);
            // Open parenthesis
            if(map.containsKey(c)){
                stack.push(c);
            }else{
              Return false (')' '}' ']' '()())}]'
               if(stack.size()==0) {return false;
               }
              // Pops the stack and gets it from the cache. The corresponding closing bracket matches the current string, if it is equal, false if it is not
               if(! map.get(stack.pop()).equals(c)){return false; }}}// Determine the final stack depth. If it is empty, it indicates that the stack is supported
        returnstack.empty(); }}Copy the code

The complexity of the

• Time complexity: O(n), where n is the length of string S

The results of

• Execution time:2Ms, at allJavaDefeated in submission76.91% of the user
• Memory consumption:36.8MB at allJavaDefeated in submission25.12% of the user

The land where I walked on silver plains and fished in rivers of green grass knows me, and if we are not strong, we perish